Near-Turing machine
A near-Turing machine is similar to a Turing machine, but has only 1 state: passing information from one cell to another is accomplished via allowing cells to change state when they are near the tape head (rather than just when the tape head is directly over the cell, as with a Turing machine). The concept was created by User:ais523 in Category:2024.
The definition in this article has no fixed syntax, making this a computational model; giving it a fixed syntax would produce an esoteric programming language.
Specification
A near-Turing machine is defined using a set of symbols, one of which is the blank symbol, and three maps:
- A symbol map that maps symbols to symbols. This determines how each symbol changes while the tape head is pointing to it.
- A nearby map that maps symbols to symbols. This determines how each symbol changes while the tape head is pointing to an adjacent cell.
- A direction map that maps symbols to tape head movements in the set {left, stationary, right, halt}. This determines how the tape head moves when pointing to a cell with a particular symbol.
Execution is based on an infinite (in both directions) tape of cells that hold symbols (and which is initially entirely filled with the blank symbol), and a tape head that points to one of the cells (initially this can be an arbitrary cell, because the initial tape has translational symmetry). Execution proceeds via repeating the following algorithm until the program halts:
- For each cell adjacent to the cell the tape head points to (not including the cell the tape head points to instead), change the symbol it contains using the nearby map (i.e. apply the nearby map to the symbol it contains, and write the result into that cell).
- For the cell the tape head points to, change the symbol it contains using the symbol map.
- Look up the symbol previously contained in the cell that the tape head points to (i.e. the symbol it contained before the previous step) in the direction map:
- If the result is "left" or "right", move the tape head one cell in that direction.
- If the result is "stationary", do not move the tape head on this cycle.
- If the result is "halt", halt the program.
Variations
One-sided near-Turing machine
The standard, "two-sided", definition of a near-Turing machine applies the nearby map to the cells on both sides of the tape head. It is possible to imagine a version of the language which only applies it on one side (typically the right side).
A two-sided near-Turing machine can almost emulate a one-sided near-Turing machine (that applies the nearby map only on the right) as follows: replace each symbol σ with two symbols σ₁ and σ₂; then transform the maps as follows:
- Symbol map: if the one-sided symbol map maps σ to τ, then if the one-sided symbol map maps σ to "right", the two-sided symbol map maps both σ₁ and σ₂ to τ₂, otherwise it maps them both to τ₁;
- Nearby map: if the one-sided nearby map maps σ to τ, then the two-sided nearby map maps σ₁ to τ₁ but σ₂ to σ₂;
- Direction map: the two-sided direction map maps both σ₁ and σ₂ to the same direction that the one-sided map maps σ to.
The basic idea is that if a cell is to the left of the tape head (i.e. the last time the tape head moved away from it, it was moving to the right), the nearby map does not affect it, but otherwise the machine acts as normal.
This construction is not perfect because the startup state does not preserve the transformation (the cells to the left of the starting position should be blank₂ but the cells to the right blank₁, but this is not a valid startup state for the two-sided near-Turing machine). The emulation is, however, perfect if the one-sided near-Turing machine is known to never go to the left of its starting position (using blank₁ as the blank symbol).
Dancing near-Turing machine
A dancing near-Turing machine does not use the "stationary" result in the direction map, meaning that the tape head has to move at every step that the machine does not halt. ais523 suspects that this restriction does not prevent the computational model being Turing-complete, although it does make programming rather more annoying and less elegant.
This was the original version of the model, before ais523 realised that allowing the tape head to remain stationary would produce a more elegant model.
Cyclic near-Turing machine and incremental near-Turing machine
In a cyclic near-Turing machine, the nearby map is a cyclic permutation of states.
An incremental near-Turing machine is basically the same, except that if the nearby map would cause a state to cycle back round to the blank state, the program halts instead. With this definition, the "halt" direction is not used in the direction map.
Both these definitions imply an ordering on the states, and mean that one of the maps does not need to be specified explicitly.
Computational class
2C can be compiled almost directly into a cyclic or incremental one-sided near-Turing machine that never moves to the left of its starting position.
The basic idea is for each near-Turing symbol to represent a character of the 2C string, and for the symbol map for each symbol to cause the tape head to wait in place for a length of time (via chaining through a sequence of auxiliary symbols that just count time) that specifies a) what the most recently seen few characters of the emulated 2C string were (including the implied zeroes), b) whether the most recently seen symbol was the rightmost end of the emulated 2C string. Each symbol of the near-Turing machine will have this information because it will have been cycled an appropriate number of times by the symbol to its left, and can thus pass the appropriate information to the symbol on the right by waiting for an appropriate length of time itself.
When the tape head is not on a symbol, it remembers a) whether it's the leftmost and/or rightmost end of the 2C string, b) what 2C character is on it, c) whether the tape head moved away rightwards or leftwards the last time it was on the cell. This makes it possible to move the tape head all the way back to the left when it reaches the end of the 2C string. (Note that when the tape head moves to the left, it will be nearby the symbol it moved left from on the next step, but it is possible to compensate for this in the symbol map.)
Program startup is fairly easy because it is the only time that a blank symbol will ever be observed on the tape. (The other blank symbols that fill the initial tape to the right of its original position will end up incremented due to being near the tape head before the tape head can reach them. The blank symbols to the left of the initial position won't be incremented, but the tape head never goes there.)
Because 2C is Turing-complete, cyclic and incremental (and thus general) one-sided near-Turing machines are also Turing-complete; and because a two-sided near-Turing machine can emulate a one-sided near-Turing machine if the tape head never moves to the left of its starting position, those must be Turing-complete too.