China
Africa
Explore chapters and articles related to this topic
When the Computer First Meets the Mind
Published in Alessio Plebe, Pietro Perconti, The Future of the Artificial Mind, 2021
Alessio Plebe, Pietro Perconti
Figure 2.3 gives an idea of how the universal Turing machine can succeed in simulating every other machine. For brevity we refer to the universal Turing machine as UTM and to the machine being simulated as TM. The UTM should read the TM as input, and this is possible since a machine is fully described by its table of transition rules. Each rule is a sequence of five symbols that belong to the domain and codomain of the transition function δ, defined in equation (2.11). In addition, the UTM should also read the input tape of the TM. Having all this information stored on its tape, the UTM can use two cells of its tape to keep trace of the current state and the current cell of the TM. These two values can be checked against each of the first two symbols in the sequence of transition rules of the TM available on the UTM’s tape. When the matching sequence is found, the following three symbols instruct what to do next: change of status; cell change; output symbol. These actions can be easily performed by the UTM on the portion of tape corresponding to the original TM’s tape. Today every computer is an implementation of the universal Turing machine with its own program that just simulates every possible program (software), stored in some memory like the internal hard disk.
What can we learn from universal Turing machines?
Published in International Journal of Parallel, Emergent and Distributed Systems, 2022
How big is such a universal Turing machine? Roughly speaking, less than 20 letters and less than 100 states are enough to make the table of a universal Turing machine. Now, if we compose a universal Turing machine U with a machine which does nothing, we obtain a new universal Turing machine whose table strictly contains that of U. Accordingly, there are infinitely many universal Turing machines. Note that it is easy to make a bigger universal Turing machine compared with another given one. Is it possible to make a smaller universal Turing machine?