patternModerate
Does forcing TMs to change all symbols they read change their power?
Viewed 0 times
allreadforcingtmspowertheydoeschangetheirsymbols
Problem
If we limit a turing machine so that it is not allowed to write the symbol that it reads would it reduce its power?
For example: $( State, A, State, Z, DIRECTION)$
$A$ cannot be the same symbol as $Z$.
For example: $( State, A, State, Z, DIRECTION)$
$A$ cannot be the same symbol as $Z$.
Solution
If you give me a standard Turing Machine, I can build a must-write-different Turing Machine that does the same thing.
I'll take the original alphabet and double it -- so for symbol $a$, I create two symbols $a_1$ and $a_2$, and for symbol $b$, I create $b_1$ and $b_2$.
Now I treat both $a_1$ and $a_2$ in the exact same way as the old TM treated $a$, except when I'm supposed to write an $a$ back onto an $a$, I check if the current symbol is $a_1$ or $a_2$ and write the other one.
We could verify that this construction will indeed mimic the behavior of the original TM (no matter what it was), so must-write-different TMs are equally powerful.
(If this is not clear, please let me know so I can explain further!)
I'll take the original alphabet and double it -- so for symbol $a$, I create two symbols $a_1$ and $a_2$, and for symbol $b$, I create $b_1$ and $b_2$.
Now I treat both $a_1$ and $a_2$ in the exact same way as the old TM treated $a$, except when I'm supposed to write an $a$ back onto an $a$, I check if the current symbol is $a_1$ or $a_2$ and write the other one.
We could verify that this construction will indeed mimic the behavior of the original TM (no matter what it was), so must-write-different TMs are equally powerful.
(If this is not clear, please let me know so I can explain further!)
Context
StackExchange Computer Science Q#7162, answer score: 15
Revisions (0)
No revisions yet.