Computation & the Turing Machine

!

Computation

!

!

Computation

!

!

Computation

!

!

Computation

!

!

Computation

!

!

Turing Machine

  1. A completely mechanical device (1928)

    envisioned by Alan Turing as an intuitive formalism to describe the non-existing phenomenon of machine driven reasoning, now known as computation.

  2. Realized into an actual design (1945)

    John von Neumann designed an electronic version to simulate the mechanical definition of a TM in a document known as First Draft of a Report on the EDVAC, 1945.

  3. Turing-complete

    TM is the most powerful computing model we know. Up to now, we don’t know any other computing models more powerful than a TM.

Turing Machine

Computational power of TM

Church-Turing Thesis

If a procedure (algorithm) can be executed by any computer, then it can be executed by a Turing Machine.


Turing Complete

If a mechanism is equivalent to TM, then it’s called Turing Complete.

Simulation of a function

!

Computable functions

A function $f$ is computable if:

  • Its input can be encoded as a binary string: $2^*$
  • Its output can be encoded as a binary string: $2^*$
  • Its evaluation can always be carried out by a TM.

!

  1. Any computable function can be implemented by a TM.

  2. Any TM is some computable function.

    Why is a TM always a function (over binary strings)?

!

Universal TM

Consider a TM: $M$.

  1. It’s a function $M:2^*\to 2^*$

  2. It’s mechanical description can be encoded as a binary string.


!

Function eval takes two inputs - a TM and an input, and it computes the output.

$$\mathrm{eval} :\mathrm{TM} \times 2^* \to 2^*$$

  1. It’s input can be encoded as binary strings.

  2. It can be carried out by a procedure.

!

By Church-Turing thesis, eval is computable, so there is a TM for it.

Definition Universal TM

The TM $\mathbf{U}$ that computes eval is called universal.

Universal TM


Modern Computer:

TM-Programming

  1. We just need a single TM, namely $\mathbf{U}$.

  2. The universal programming language is the encoding of $M$.

Summary

!

back
Programming Languages, Ken Pu