Abstract machines {Turing machine} [Herken, 1988] [Turing, 1937] run algorithms that have finite numbers of elements (typically 0 and 1) and instructions to execute (rule) and use only rational numbers, countable irrational numbers, and rational approximations to irrational numbers. Turing machines have a tape, a tape reader/writer with an internal state, and rules.
tape
The tape contains all input and receives all output.
The tape has only 0 or 1 at each of an infinite number of tape positions. The tape has infinitely many 0 positions and at least one 1 position.
The tape holds the input data, rules, and output.
Tape position combinations represent numbers, text, number-and-text separator symbol (comma), number-and-text termination symbol (blank), minus sign, plus sign, division sign, move right one square, move left one square, read, write, and stop. For example, the tape position combination ...001100... can represent the decimal number 3, the letter C, or the symbol minus sign. Coding is unique and unambiguous.
Combinations of tape position combinations represent numbers, words, sentences, mathematical formulas, dates, and arrays. Coding can represent all rational numbers and can represent approximations to countable irrational numbers, using minus sign, plus sign, and division sign. However, most irrational numbers are not computable by Turing machine, which never stops if something is uncountable.
The tape starts with all input data and instructions on one tape-reader side. Input data and instructions make a finite binary number. Instructions and input data depend on each other.
The tape ends with all output data on one tape-reader side. Output data makes a finite binary number. The other tape side includes intermediate calculations, modified input data, and rules.
Note: Turing machines have no need for more than one tape or tape reader, because multiple ones are always equivalent to one.
tape reader/writer
The tape reader/writer reads the 0 or 1 at the current tape position and writes the same or opposite symbol there (overwriting the previous symbol).
After writing, the tape reader/writer changes to the same or another internal state.
After writing, the tape reader/writer moves right or left one tape position. It can eventually move to any tape position, and go there any number of times, but does not have to go all positions or any one tape position.
internal state
The internal state is a combination of previously read symbols and is a finite binary number. Turing machines have a finite number of internal states, to which it can return any number of times, but does not have to reach all states or any one internal state.
The internal state and the currently read symbol determine the rule to apply after reading. Therefore, each internal state has a pair of rules, one for reading 0 and one for reading 1. Turing machines never reach an internal state that has no rules.
rules
For the current internal state and currently read symbol, rules (instructions) determine what the tape reader/writer does after reading the tape symbol: 1. Keep the same, or change to a different, internal state. AND 2. Change, or do not change, the symbol at the tape position. AND 3. Move tape one position to right or left. AND 4. Stop or do not stop.
Rules depend on input data. The number of rules is two times the number of internal states. Turing machines have a finite number of rules (because they have a finite number of internal states). Rules are finite binary numbers.
Rules can repeat any number of times. Turing machines do not have to use all rules or any one rule.
Turing machines must be able to get to at least one stop rule and so end operation.
output
After a stop rule runs, the tape has output data to the left or right of the final tape position. The output is a number, symbol, letter, word, phrase, sentence, date, or boolean yes or no (or an array of them). The tape's other side has intermediate calculations, modified input data, and the rules.
Turing machines must have at least one 1 in an output-side tape position.
operation
The tape reader/writer starts in an internal state at a 0 tape position on the right or left side of the input-data-and-rules tape positions.
The tape reader/writer reads the 0 at that tape position and, using the rule for the internal state and the 0 symbol, changes to the same or another internal state, prints the same or opposite symbol at the same position, moves the tape one position to right or left, and stops or does not stop.
Next, the tape reader/writer reads the 0 or 1 symbol at the new tape position and, using the rule for the current internal state and read symbol, changes to the same or another internal state, prints the same or opposite symbol at the same position, moves the tape one position to right or left, and stops or does not stop.
The tape reader/writer then continues reading symbols and following rules until it comes to a stop, which it must do or else it is not a valid Turing machine.
After the stop rule, the answer is to the left or right of final tape position. The other tape side has intermediate calculations, modified input, and rules.
Turing machines begin with a finite binary number, for inputs and rules, and produce a finite binary number, for output.
restrictions
Turing machine must have at least one rule that leads to STOP, must not move to non-existent internal state, must use and make only coded sequences of marked and blank squares, and must have at least one marked square on output side.
It is difficult to make input data and rules that reach STOP and so make Turing machines.
universal Turing machine
Some Turing machines (universal Turing machine), with special input data and rules on the tape, can imitate any Turing machine.
A simple cellular automaton and a special initial state can make a universal Turing machine.
computers and Turing machines
Computers are efficient universal Turing machines.
brains and Turing machines
Rather than one tape reader/writer, brains have many readers and writers acting continually and simultaneously. Upstream neurons automatically write to downstream neurons. Downstream neurons automatically read upstream neurons.
Rather than serial processing, neurons update simultaneously.
Rather than reading or writing one tape position at a time, brains continually and simultaneously read and write to all neurons.
Rather than separate tape positions, neurons interact.
Rather than a tape with an infinite number of positions, brains use a three-dimensional region with a finite number of locations.
Rather than two symbols to read, neuron synapses have synaptic strengths, which change continually.
Rather than two symbols to write, neurons send impulse rates, which change continually.
Rather than one internal state, brains have many internal states. Each neuron has a state, and each neuron set has a state. Brain, neuron set, and neuron internal states are complex and interact.
Rather than a small fixed set of rules, brains use many and more complex rules for changing state, reading, writing, moving, and stopping, and rules can interact and change.
Rather than stopping at a STOP rule, brains stop consciousness when they fall asleep but still process information.
Rather than the ability to perform any algorithm with a finite number of elements and instructions, brains may not be able to perform some algorithms, can perform non-algorithmic functions, and can use an infinite number of elements and instructions.
equivalences
Turing machines can compute partial recursive functions that use recursively enumerable element sets. Turing machines can approximate functions that are not partial recursive functions with partial recursive functions.
Because quantitative grammars involve only integers, Turing machines can be equivalent to quantitative grammars, Post grammar, and lambda calculus.
example 1: Turing Machine with One State, Two Rules, and One Marked Square
Rule 1: If State 1 and unmarked square, change to internal state 1, do not change the mark, move tape one square to right, and do not stop. Rule 2: If State 1 and marked square, change to internal state 1, do not change the mark, move tape one square to right, and stop. For example, see Figure 1 through Figure 5.
example 2: Turing Machine with Two States, Three Rules, and Two Marked Squares
Example Turing machine can calculate 1 + 1 = 2 or 01 + 01 = 10 in binary code. Infinite tape has square series that define rules. Then it has square series that define input: 0s, up to 1, followed by 1, and then 0s: ...00000110000... Reader starts to right of rules, reads rules, and ends to right of rules and left of the ...11..., in internal state 0. Rules for this Turing machine are as follows. If current state is 0, and 0 is read, move right to next input. If current state is 0, and 1 is read, move right to next input and add 1 to state. If current state is 1, and 1 is read, move left to next input and add 1 to state and stop. To tape-reader right is the answer 10.
example 3: Turing Machine with Two States, Four Rules, and Two Marked Squares
Example Turing machine can calculate 1 + 1 = 2 or 01 + 01 = 10 in binary code. Infinite tape has square series that define rules. Then it has square series that define input: 0s, up to 1, followed by 0, followed by 1, and then 0s: ...000001010000... Reader starts to right of rules, reads rules, and ends to right of rules and left of the ...101..., in internal state 0. Rules for this Turing machine are as follows. If current state is 0, and 0 is read, move right to next input. If current state is 0, and 1 is read, move right to next input and add 1 to state. If current state is 1, and 0 is read, move right to next input. If current state is 1, and 1 is read, move left to next input and add 1 to state and stop. To tape-reader right is the answer 10.
Mathematical Sciences>Computer Science>Systems
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0224