3 ms·
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
by Sharlin 7y ago
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.
- daveFNbuck 7y agoThe 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.