Instead of walking along an infinite tape, modify a Turing Machine to walk along an infinite binary tree. In each state transition, the head can move to the parent or to one of the two children (or possibly stay in place). Data can be written at each node, analogous to tape cells.
Perhaps make available in the state whether a node is a left or right child.
The tree could have a root node, analogous to a Turing machine tape that is only infinite in one direction, or the parents could continue upwards forever, analogous to a tape that is infinite in both directions. A regular Turing machine can be simulated by just traversing the leftmost nodes.
This machine model seems attractive to write real programs for because it can address exponential amounts of memory in linear time, unlike the traditional Turing machine which takes linear time to get to an address.
No comments :
Post a Comment