Re:The Power of One-State Turing Machines (2018)
by Sharlin on Saturday November 23, 2019 @05:12AM
(#21613372)
Not arbitrary. Modulo some constant k, the size of the tape alphabet. They're just choosing as the tape alphabet the set { 1, 2, …, k-1 }, and as the transition function one that maps each n to n+1 mod k. It's just a lookup table.
[ Parent
| on HN ]
Re:The Power of One-State Turing Machines (2018)
by daveFNbuck on Saturday November 23, 2019 @10:28AM
(#21614572)
The transition function can only do modular addition within a cell, but the paper also describes how to build a k-ary counter.
If your single state has the increment lookup table for a single cell, you just need to move to the next cell to do carries, and move to the previous cell to leave the counter when you're done. A special carry character is written instead of zero to make sure you leave the whole counter, and you convert it to zeroes as you leave.