Turing Machines


k-tape turing machine

Turing machines (TM) were introduced by Alan Turing in 1936. A turing machine can be described by a tuple (T, Q, F) containing:

  • A finite set T (alphabet) of symbols in which a blank symbol, a start symbol and the numbers 0 and 1 are included *.
  • A finite set Q of possibles states for the register in which q_0 and q_halt are included.
  • A function F: Q x T^k –> Q x T^(k-1) x {Left, Stay, Right} describing the rules used by the turing machine in each step.

This definition of a turing machine is robust because this computational model can simulates the others (single-tape turing machines, bidirectional turing machines, …) efficiently.

* The definition of TM given in the lecture restricts the alphabet to {0, 1, blank symbol, start symbol}.

Simulate Using In time
TM using alphabet T TM using the alphabet {0, 1, blank symbol, start symbol} 4 log |T| t(n)
k-tape TM single-tape TM 5 k t(n)^2
bidirectional TM unidirectional TM 4 t(n)

Definition: (Computing a function and running time)
f: {0,1}* –> {0,1}*
t: N –> N
N = { 0, 1, 2, … }
n = |x|
The TM M computes f in time t(n) if for all the strings x in {0,1}* the computation of M on the input x halts in a number of steps less than or equal to t(|x|) with f(x) in the output tape.

Definition: (Languages/Decision Problems)
L is a subset of {0,1}*
F_L defines the language or decision problem L if F_L(x) = { 1 if x is in L and 0 if x is not in L}.

A TM M decides L if it computes F_L.

A complexity class is a set of functions that can be computed within given resource bounds.

Definition: (The class DTIME)
DTIME(t(n)) = {L | some TM that runs in time c t(n) and decides L}

(The class P)
P = U DTIME(n^c)

The universal turing machine simulates all the other TM by representing them as strings.

Theorem: (Efficient universal Turing machine)
M_alpha is the TM represented by the string alpha in {0,1}*.
There is a TM U such that for all x, alpha in {0,1}*, U(x, alpha) = M_alpha(x). Moreover, if M_alpha halts in input x within t(n) steps then U halts on input (x, alpha) within Cm t(n) log t(n) steps, where Cm depends on the turing machine.

See also:

* Sanjeev Arora and Boaz Barak, Computational Complexity, Capther 1.


One response to this post.

  1. Hey, estudiando tu curso de complejidad computacional :D.

    Interesante como esto pone artículos relacionados… voy a ver qué están hablando del Busy Beaver.

    (Por cierto, ¿qué modelo de MT están usando en ese curso? El dibujo parece ser de uno con k cintas).




Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: