Thanks for taking the time to look at my Wolfram Summer Camp project - I'm glad you enjoyed it :)

Analysing statistics is a great idea - I looked at a few statistical features very briefly (like what percentage of a sample combinators of a given size halt after n steps - graphs are in the post) but never tried to explicitly use those (or things like growth rate) as features for halting classification.

I'm currently working on a few improvements to the method (one of which being an expansion of the machine learning model to predict halting for combinators of arbitrary size, albeit with lower accuracy) and correcting one or two minor errors - hopefully this should be done soon.

After these, I might give classification with 'crude' statistical tests a go at some point, as well as using features like growth rate / depth of combinator to train e.g. a logistic regression classifier on the combinators. There is a chance that the neural network might only be detecting things like growth rate when looking at rasterised images of combinators, but I'm hopeful that it might be detecting more 'complex' features of combinator structure, particularly as a halt/no halt classifier trained only on initial combinator expressions (represented as strings) managed to achieve ~70% accuracy.

On a similar but tangential note (a few rambling thoughts):

Speaking of "[examining] a few steps and [seeing] if the expression grows quickly or if it already halts", Lathrop proved that

"it is possible to compute some value K where for some arbitrary predetermined confidence (1-?) and accuracy (1-?), a program that does

A. Input a Turing machine M and program I.

B. Simulate M on I for K steps.

C. If M has halted then print 1, else print 0.

D. Halt.

has a probability greater than (1-?) of having an accuracy (when predicting whether or not a program will halt) greater than (1-?)" (https://www.ics.uci.edu/~rickl/publications/1996-icml.pdf).

So in a way, this type of statistical analysis of (combinators / turing machines) is possible, and would be more accurate than a modern 'machine learning' algorithm if k is set high enough - however, if k is large this would entail evaluating the combinator for many steps which would be computationally intensive and impractical. In this case a machine learning model trained on a dataset labelled using a large value of k could potentially deliver much faster results, albeit with a (slightly lower) accuracy.

That said, one of the aims of this project is to see if there are other features of a combinator which might make it more / less likely to halt without having to manually evaluate the combinator - in this regard the machine learning approach is less of practical importance but more a proof-of-concept demonstrating that there may be features of (the initial combinator expression / its initial growth) that suggest whether or not it will halt. With this in mind, analysing specific statistical features could well prove useful in trying to determine which features suggest whether or not an expression will halt.

Please do let me know if you have any further thoughts on any of the above - I'd be very interested to hear what you have to say.

Kind regards,

Euan