SK Combinator Expression Analysis

Expression:

s[k][k][s[s[s][k][k]][s[s[k[k]]]]][s[k][k[s]][s[k[k]]][s][k[k]]][s[k][s[k[s[k]]][s][s[s[s]][s[s][s[s][s[s][k]]]]]][s]][k[s][k[s]]]

Visualisation:

Initial state and first 5 steps of evaluation:

The nth row of the image represents the nth step of evaluation of the combinator.

Graph of Evaluated Expression Lengths:

As the combinator is evaluated, its length changes. This graph plots length of combinator against number of steps of evaluation.

Statistical Analysis of Halting Time:

This combinator has 44 leaves. This combinator falls within the 68th percentile of a random sample of 1000 combinators with leaf size 44, halting after 11 steps - on average, 68.6% of combinators from this sample halt before this one. A graph demonstrating this follows:

Machine Learning Analysis of Halting:

A machine learning model (using logistic regression) has been trained on a sample of 1456 rasterised images of the first 5 steps of random SK combinator expressions with varying leaf lengths, achieving 87.7% accuracy when classifying a test set of 1454 random SK combinator expressions as halting or non halting (before 40 steps).

This particular expression, which halts after 11 step(s), is classified as having a Indeterminate% probability of halting, and a Indeterminate% probability of not halting (before 40 steps).

Evaluated expression:

Halted in 10 step(s)

0	s[k][k][s[s[s][k][k]][s[s[k[k]]]]][s[k][k[s]][s[k[k]]][s][k[k]]][s[k][s[k[s[k]]][s][s[s[s]][s[s][s[s][s[s][k]]]]]][s]][k[s][k[s]]]
1	k[s[s[s][k][k]][s[s[k[k]]]]][k[s[s[s][k][k]][s[s[k[k]]]]]][k[s[k[k]]][k[s][s[k[k]]]][s][k[k]]][k[s][s[k[s[k]]][s][s[s[s]][s[s][s[s][s[s][k]]]]][s]]][s]
2	s[s[s][k][k]][s[s[k[k]]]][s[k[k]][s][k[k]]][s][s]
3	s[s][k][k][s[k[k]][s][k[k]]][s[s[k[k]]][s[k[k]][s][k[k]]]][s][s]
4	s[k][k[k]][k[k][k[k]][s[k[k]]]][s[s[k[k]]][k[k][k[k]][s[k[k]]]]][s][s]
5	k[k[k][k[k]][s[k[k]]]][k[k][k[k][k[k]][s[k[k]]]]][s[s[k[k]]][k[s[k[k]]]]][s][s]
6	k[k][k[k]][s[k[k]]][s[s[k[k]]][k[s[k[k]]]]][s][s]
7	k[s[k[k]]][s[s[k[k]]][k[s[k[k]]]]][s][s]
8	s[k[k]][s][s]
9	k[k][s][s[s]]
10	k[s[s]]