Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
WolframInstitute`TuringMachine`
TuringMachineWorstCasePlot  |
| |
▪
The envelope (a step function) takes the maximum running time over all inputs of each length in base k, giving an upper bound on cost as the input grows; the underlying per-input runtimes come from with the property.
"Steps"
▪
The option toggles the envelope. Choose an input range in which every machine halts within n steps — non-halting inputs have infinite runtime and cannot be placed on the plot.
"ShowEnvelope"
Examples
(0)
 |
|
Plot the runtime of the s=3, k=2 rule 600720 with its worst-case envelope, over an input range it fully halts on:
In[1]:=
 | TuringMachineWorstCasePlot |
Out[1]=
""