Predict halt/no-halt for 5-state TM?

General
1

Speaking of trying to predict total stopping time with better than baseline accuracy …

Have Busy Beaver folks tried to predict halt/no-halt from the description of a 5-state, 2-symbol TM? I’m sure there are many “give away” features of TMs that halt. Probably these arose in the process of creating the BB(5) proof.

Can an ML model automatically locate those features, given 88 million TM descriptions each labeled with class 0 (halt) or 1 (no-halt)?

It’s possible to make a traditional 90% train, 10% test setup … or alternatively, don’t divide the data, but rather see who can induce the shortest program that prints the entire dataset verbatim, along the lines of the Hutter Prize for text.

(BTW, is there a pointer to such data in a single downloadable txt file?)

1 Like
2

You can get a full list of all TMs (in Tree Normal Form) at https://docs.bbchallenge.org/CoqBB5_release_v1.0.0/ .

I don’t know if anyone has tried doing ML prediction of behavior based on transition table. In general, it is not an easy problem because very slight differences in instructions generally lead to huge differences in runtime / halting status. I wrote about this issue in a blog post several years ago. At the time my dad and I used Genetic Programming and Simulated Annealing to find new champions, but at the end of the day I think we would have been more successful by just doing exhaustive search.

3

@sligocki great, thanks very much for the pointers