Transcript: Difference between revisions
Jump to navigation
Jump to search
(Created page with "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 sh...") |
(Used Template:Stub) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{Stub}} | |||
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 /> | |||
Latest revision as of 22:40, 10 August 2025
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