I want to built a TM, which can remember its position $n$, jump to the beginning of the tape and then iterate to the right until it's on the position $n-1$ (I can't use step to the left). I don't know how to achieve this position remembering and then comparing it to the current position. Is it somehow possible to achieve this behaviour with a TM?
Asked
Active
Viewed 133 times
0
-
How many tapes does your TM have? – Alex Vong Dec 14 '17 at 19:05
-
@AlexVong Just one. – T.Poe Dec 14 '17 at 19:07
-
1can you replace the alphabet $A$ with a different alphabet $A\times{0,1}$? – Hagen von Eitzen Dec 14 '17 at 19:15
-
Yes, it's possible. @HagenvonEitzen – T.Poe Dec 14 '17 at 19:19
-
The point to do anything you'd want is really to build an universal TM $u$. Do you see how running a TM yields a sequence of states (or integers) $a_n$ ? Then the transformation law $a_{n+1} = TM(a_n)$ can be simulated in $u$. – reuns Dec 14 '17 at 19:31