Universal Turing Machine (UTM)

From GM-RKB
Jump to navigation Jump to search

A Universal Turing Machine (UTM) is a Turing machine that can simulate any other Turing machine.



References

2020

  • https://web.mit.edu/manoli/turing/www/turing.html
    • QUOTE: The problem with Turing Machines is that a different one must be constructed for every new computation to be performed, for every input output relation.

      This is why we instroduce the notion of a universal turing machine (UTM), which along with the input on the tape, takes in the description of a machine M. The UTM can go on then to simulate M on the rest of the contents of the input tape. A universal turing machine can thus simulate any other machine.

      Turing Machine Schematic

      I learned about Turing Machines the first term of my sophomore year at MIT (Fall 96), in 6.004 (Computational Structures), the best class ever conceived. It was late one night when I was starting my problem set on writing a turing machine to compute some operation. To test my result, I figured I could code up a Universal Turing Machine in Scheme to help me do my problem set. I could then feed it my description and a sample input, and it would simulate any machine for me. To my surprise within two hours, the program was working, and i could start the rest of my problem set (You can read on, or simply download the scheme code).

2016

  1. Arora and Barak, 2009, Theorem 1.9

1936