Timeline for Turing machine with "move to origin" instead of "move left"
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 3, 2022 at 10:40 | comment | added | Christian Singer | @hermi Marking the symbol a at the position from which we want to move to the left as special can be done by putting a dot on top dot $\cdot$ of it. We shift the input to the right by substituting each symbol on the tape by the symbol that preceeds it (leftmost symbol is replaced by a blank). During substitution we can make sure that the turing machine only substitutes the symbol and leaves the special marker $\cdot$ in place. Example : $aa\dot{b}b \rightarrow \sqcup a\dot{a}bb$ | |
| May 31, 2021 at 5:07 | comment | added | hermi | But how can we shift the tape to the right and keep a special position? | |
| Apr 24, 2020 at 14:08 | history | edited | Yuval Filmus | CC BY-SA 4.0 |
added 67 characters in body
|
| Apr 24, 2020 at 6:48 | history | answered | Yuval Filmus | CC BY-SA 4.0 |