Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is this a Turing-complete machine?

  1. Jul 13, 2018 #1
    Say a Turing machine is simulated by the following rules:
    • A number of states can be defined.
    • Each state is defined by :
      • specifying what the head writes in the current cell in case of each symbol of the alphabet
      • specifying where the head moves (left or right) in case of each symbol of the alphabet of the current cell
      • specifying which state the current state transitions to in case of each symbol of the alphabet

    Is this a Turing-complete (ignoring memory limitations) machine? I have seen very different Turing machines on the Internet by some people. For example palindrome checking-capable machine which, at some point during its procedure moves the head by more than 1 cell. Or at some other point it searches for a specific value on the tape. Both of these tasks seem impossible on the approach I outlined. Does it make the approach I described result in a non-Turing-complete machine?
  2. jcsd
  3. Jul 13, 2018 #2
    I believe your version of the turing machine is the most common. It's typically pretty easy to prove that other types are equivalent to this type.
    For example:
    Using more different symbols. You can encode the states in binary as groups of symbols next to each other, you will need more states of course.
    A single state of a 4-symbol machine will take 3 states of a 2-symbol machine that scans the tape to split the execution in 4 different paths, depending on if there's 00, 01, 10 or 11 on the tape. Then each of those four paths may need several extra states to write the 2 output symbols that encode the single symbol on the 4-symbol machine, and move the tape to the right starting place for the next step.

    A Turing machine with more than one tape is harder. You must interleave the symbols of more than one tape on a single tape, as well as markers to find the current positions of all the tapes. For every step that the multi tape machine makes, the single tape machine will have to search for all the start of tape markers.
    A multi-tape TM may be dramatically faster than a single tape machine, but is still equivalent.
    Turing machines have also been proven equivalent to mant other kinds of abstract machines. Register machines, random access machines (use a computation to address memory), machines with stored programs, etc.
  4. Jul 13, 2018 #3


    User Avatar
    Science Advisor
    Gold Member

    As you're talking about a Turing - complete machine, you mean simulating a Turing machine using e,g. a programming language. Now, a Turing - complete programming language (or system in general) has to be able to give the ability to create and run any program that a Turing machine can run, given enough time and memory. Now, in the rules you define for the TM, I see a finite set of states, an input alphabet, a tape alphabet, a transition function - all these implied, but you also need a start state, a blank symbol and a set of final states.

    There are various programming tricks for a TM in order to simulate a real computer, like multiple tracks: if you think of tape symbols as vectors with ##m## components and each component taking values from a finite alphabet, this makes the tape appear like having ##m## tracks, marking: you use an extra track in order to mark certain positions, state caching: you can also make state a vector construction with first component being the control state. Also, as willem2 points out, you can simulate a multi-tape Turing machine which will be harder but way faster.
    Last edited: Jul 13, 2018
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?