Algorithm and Complexity 2, année 2024

Computability

Some machines can simulate other machines. For example, our computers are able to simulate Python virtual machine. The Python virtual machine can simulate a Turing Machine and it is even easy to do so. Several external modules offer class to simplify this: turing_machine.

If we abstract away memory constraint, it is thus possible to simulate a Turing Machine on a Python Virtual machine. Hence, any Turing-Computable language is also computable by a Python program (and thus by the actual machine actually executing the code).

It can be shown (but it is not completely easy) that a Turing machine can also simulate a Python program. Hence, the two notions of computation represented by both Turing Machine and Python programs actually match.

This fact is neither specific to Python or Turing machine but actually to any discrete model of computation. We can (probably) simulates any of those model with a Turing machine, and if these models are expressive enough they can also simulate a Turing machine.

It is not really known if any physical machine can compute more than a Turing machine (neither if the question can be made formal). It is however highly believed to be a universal limit of computation that arose in many different shapes, as exposed by the Church Thesis.

More on the subject.

When a given model of computation has the ability to simulate Turing machines, we say that it is Turing-hard. If the converse is also true, that is, if it can also be simulated by Turing machines, we say that it is Turing-complete.

The terminology behind hard and complete will be investigated further in future coming lectures.

Universal Turing machine

It is possible to simulate a Turing machine directly with Turing machine. It is the main result of the Seminal of Turing (1936).

It has many impact on the overall comprehension of the nature of computation. In particular, it allows to prove the undecidability of the Halting problem: there exists no Turing machine that can decide if a Turing machine in input will halt on the empty input.

Although the result holds for Turing Machine, it is not really dependent on the model of computation. We can even prove it using Python syntax.

def halt(f, x):
    """
        Return True if f(x) stops in finite time else return False
    """
    pass # I don't know how to do that :(

def g(f):
    if halt(f, f):
        while True:
            pass
    else:
        return

g(g) # Does it stop? Does it loop infinitly?

Exercises

1. Show that a Turing Machine with two tapes can be simulated with one tape Turing machine.

2. Show that a Turing Machine with \(k\)-tapes can be simulated with one tape Turing machine.

3. Show that Turing-Computable languages are closed under Boolean operations.

Turing-Complete by accident

It often happens that some limited computing power is embedded into some software. Then, step by step, developers add small functionalities to make it more convenient. At some point it become Turing Complete by accident.

This website provides a fun list of known accidental Turing-complete models of computation.

Compiled the: mar. 21 janv. 2025 22:04:08 CET