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.
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.