Construction of Universal Turing Machine

Universal Turing Machine
  • The input tape: a read-only tape containing the input, which is never overwritten;
  • The description tape: a tape containing the description of M, which is written once at initialization time and never overwritten afterwards;
  • The working tape: a tape whose contents correspond to the contents of M’s tape, translated into-bit blocks of binary symbols separated by commas, as the computation proceeds.
  • The state tape: a tape describing the current state of M, encoded as an-bit block of binary symbols
  • The special tape: a tape containing the binary encodings of the special states {halt, yes, no} and the “directional symbols” {←, →, −}.
  • Copy the description of M onto the description tape
  • Copy the input string x onto the working tape, inserting commas between each-bit block.
  • Copy the starting state of M onto the state tape.
  • Write the identifiers of the special states and directional symbols onto the special tape.
  • Move each cursor to the leftmost position on its respective tape.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store