Incoming links: Turing machine acceleration
Non formal proof with a program March 2023: www.sligocki.com/2023/03/13/skelet-1-infinite.html Awesome article that describes the proof procedure.
The proof uses Turing machine acceleration to show that Skelet machine #1 is a Translated cycler Turing machine with humongous cycle paramters:
- start between 50-200 M steps, not calculated precisely on the original post
- period: ~8 billion steps
Turing machine acceleration refers to using high level understanding of specific properties of specific Turing machines to be able to simulate them much fatser than naively running the simulation as usual.
Acceleration allows one to use simulation to find infinite loops that might be very long, and would not be otherwise spotted without acceleration.
This is for example the case of www.sligocki.com/2023/03/13/skelet-1-infinite.html proof of Skelet machine #1.
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.