Comment by avmich

So, about 88 millions of machines is left to test. We're interested in any, which runs longer than about 47 millions steps. Multiplying we get about 4.2e15 steps at worst. Can't we brute force the solution? It's like 5 million seconds - or less than two months - 1 billion steps a second, which looks doable for a modest system, and we don't even need much memory...