Simulating Turing machines on Maurer machines (Q2480963): Difference between revisions

This paper presents three ways to simulate Turing machines on Maurer machines, which give insight into the connections between Turing machines, Maurer machines and real computers: 1. The Maurer machine on which Turing machines are simulated has the most obvious operations for simulation of Turing machine. Unlike real computers, the Maurer machine, used for simulation, has operations on an infinite input region or an infinite output region. 2. The Maurer machine used for simulation of Turing machines has only operations with a finite input region and a finite output region. 3. The Maurer machine used for simulation of Turing machines has also only operations with a finite input region and a finite output region but there is another kind of simulation of the transition function of Turing machines: first stored in the memory of the Maurer machine and then executed under control of a multi-thread that makes the head position part of the operations. The multi-thread forks off every head position a control thread of itself on the head reaching the preceding position for the first time. This way illustrates that some main concepts of contemporary programming, multi-thread and thread, have an interesting theoretical application.