Transcript: Difference between revisions
Jump to navigation
Jump to search
m (ref section) |
m (Capitalization) |
||
| Line 1: | Line 1: | ||
A [[Turing machine]] '''transcript''' or '''transition history''' is the sequence of transitions that the TM executes when started on a blank tape. Halting TMs have finite transcripts, infinite TMs have infinite transcripts. A finite description of an infinite TM transcript is one way to specify the forward behavior of that TM precisely. | A [[Turing machine]] '''transcript''' or '''transition history''' is the sequence of transitions that the TM executes when started on a blank tape. Halting TMs have finite transcripts, infinite TMs have infinite transcripts. A finite description of an infinite TM transcript is one way to specify the forward behavior of that TM precisely. | ||
[[Shift rule]]s lead to repeated segments of a TM transcript and vice-versa every repeated segment in a transcript corresponds to a shift rule. If we augment TM transcripts to detect the difference between initial and written blank symbols, then all [[ | [[Shift rule]]s lead to repeated segments of a TM transcript and vice-versa every repeated segment in a transcript corresponds to a shift rule. If we augment TM transcripts to detect the difference between initial and written blank symbols, then all [[translated cycler]]s can be detected by noticing a repeat in the transcript that contains at least one initial blank.<ref>Shawn Ligocki. 2024. "TM Transcripts". https://www.sligocki.com/2024/06/12/tm-transcripts.html</ref> | ||
== References == | == References == | ||
Revision as of 17:32, 13 November 2024
A Turing machine transcript or transition history is the sequence of transitions that the TM executes when started on a blank tape. Halting TMs have finite transcripts, infinite TMs have infinite transcripts. A finite description of an infinite TM transcript is one way to specify the forward behavior of that TM precisely.
Shift rules lead to repeated segments of a TM transcript and vice-versa every repeated segment in a transcript corresponds to a shift rule. If we augment TM transcripts to detect the difference between initial and written blank symbols, then all translated cyclers can be detected by noticing a repeat in the transcript that contains at least one initial blank.[1]
References
- ↑ Shawn Ligocki. 2024. "TM Transcripts". https://www.sligocki.com/2024/06/12/tm-transcripts.html