Transcript: Difference between revisions
Jump to navigation
Jump to search
m (ref section) |
(Used Template:Stub) |
||
| (One intermediate revision 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 == | ||
<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