A Turing machine decider is a program that decides if one or more Turing machines halts of not.
Of course, because what we know about the halting problem, there cannot exist a single decider that decies all Turing machines.
E.g. The Busy Beaver Challenge has a set of deciders clearly published, which decide a large part of BB(5). Their proposed deciders are listed at: discuss.bbchallenge.org/c/deciders/5 and actually applied ones at: bbchallenge.org.
But there are deciders that can decide large classes of turing machines.
Many (all/most?) deciders are based on simulation of machines with arbitrary cutoff hyperparameters, e.g. the cutoff space/time of a Turing machine cycler decider.
The simplest and most obvious example is the Turing machine cycler decider
Turing machine regex tape notation is Ciro Santilli's made up name for the notation used e.g. at:Most of it is just regular regular expression notation, with a few differences:
- denotes the right or left edge of the (zero initialized) tape. It is often omitted as we always just assume it is always present on both sides of every regex
A,B,C,DandEdenotes the current machine state. This is especially common notation in the context of the BB(5) problem<and>next to the state indicate if the head is on top of the left or right element. E.g.:indicates that the head11 (01)^n <A 00 (0011)^{n+2}Ais on top of the last1of the last sequence of n01s to the left of the head.
This notation is very useful, as it helps compress long repeated sequences of Turing machine tape and extract higher level patterns from them, which is how you go about understanding a Turing machin in order to apply Turing machine acceleration.
Bibliography: discuss.bbchallenge.org/t/decider-cyclers/33
Example: bbchallenge.org/279081.
These are very simple, they just check for exact state repetitions, which obviously imply that they will run forever.
Unfortunately, cyclers may need to run throun an initial setup phase before reaching the initial cycle point, which is not very elegant.
Also, we have no way of knowing the initial setup length of the actual cycle length, so we just need an arbitrary cutoff value.
And unfortunatly, this can lead to misses, e.g. Skelet machine #1, a 5 state machine, has a (translated) cycle that starts at around 50-200M styeps, and takes 8 trillion steps to repeat.
Bibliography: discuss.bbchallenge.org/t/decider-translated-cyclers/34
Like a cycler, but the cycle starts at an offset.
To see infinity, we check that if the machine only goes left N squares until reaching the repetition, then repetition must only be N squares long.
Described at: www.sligocki.com/2022/06/10/ctl.html
Articles by others on the same topic
There are currently no matching articles.