automatas

Máquinas de Turing Indecidibilidad Incomputabilidad

Máquinas de Turing Indecidibilidad Incomputabilidad
Definición y ejemplos Variantes Recursivo vs. recursivamente enumerable

Entscheidungsproblem I
AUTÓMATAS Y LENGUAJES FORMALES
MÁQUINAS DE TURING Y
DECIDIBILIDAD

Las máquinas de Turing se inventaron para contestar una pregunta abierta
en lógica matemática:
Sean α1 , . . . , αnfórmulas del cálculo de predicados a las que
llamaremos axiomas.
Sea θ otra fórmula a la que llamaremos candidato a teorema.

Francisco Hernández Quiroz

Queremos un método para poder contestar la pregunta

Departamento de Matemáticas
Facultad de Ciencias, UNAM
E-mail: fhq@ciencias.unam.mx
Página Web: www.matematicas.unam.mx/fhq

¿α1 , . . . , αn |= θ?
(Que se lee “¿θ es una consecuencialógica de α1 , . . . , αn ?”)
Éste es el problema clásico de la decisión o Entscheidungsproblem.

Posgrado en Ciencia e Ingeniería de la Computación

Francisco Hernández Quiroz

Autómatas y Lenguajes Formales

Máquinas de Turing

1 / 46

Francisco Hernández Quiroz

Autómatas y Lenguajes Formales

Máquinas de Turing Indecidibilidad Incomputabilidad

2 / 46

Máquinas de TuringIndecidibilidad Incomputabilidad

Definición y ejemplos Variantes Recursivo vs. recursivamente enumerable

Máquinas de Turing

Definición y ejemplos Variantes Recursivo vs. recursivamente enumerable

Procedimiento efectivo

Máquinas de Turing (TM)

El método que buscamos deberá tener las siguientes características:
1

2

Deberá ser “mecánico”: su aplicación se basará en reglas que sesiguen sin necesidad de interpretación o de “inspiración”.

3

El método deberá especificarse de manera finita.

4

Una máquina de Turing es un mecanismo muy simple que consiste en una
cinta de lectura y escritura, una cabeza de lectura y escritura que recorre
esta cinta (y que puede estar en diferentes estados) y una función que regula
los movimientos de la cinta.

Deberá expresarseen términos tan formales como las instancias del
problema.

Los recursos utilizados deben ser finitos tanto espacial como
temporalmente y, de preferencia, deben poder acotarse con
anticipación.

a

Church y Turing demostraron que no existe un método para resolver el
Entscheidungsproblem que cumpla con lo anterior.
De paso, inventaron dos de los modelos más populares de computación.Francisco Hernández Quiroz

Autómatas y Lenguajes Formales

Máquinas de Turing

3 / 46

Francisco Hernández Quiroz

a

b

b

c

c
↑
q

Autómatas y Lenguajes Formales

···

Máquinas de Turing

4 / 46

Máquinas de Turing Indecidibilidad Incomputabilidad

Máquinas de Turing Indecidibilidad Incomputabilidad

Definición y ejemplos Variantes Recursivo vs. recursivamenteenumerable

Definición y ejemplos Variantes Recursivo vs. recursivamente enumerable

Definición formal

Aceptación y rechazo I
Una configuración es una terna

Una máquina de Turing está formada por los siguientes elementos:
un conjunto de estados Q;

(q, α

un alfabeto de entrada Σ;
una función de transición δ : Q × Γ → Q × Γ × {→, ←}

(s, α

los estados inicial, de aceptación y derechazo s, t, r ∈ Q,
respectivamente;
∈ Γ − Σ;

, 0)

α ∈ Σ∗ .

α[n]
el n-ésimo símbolo de la cadena α y

Es imposible moverse a la izquierda del símbolo de inicio.
Los estados de aceptación y rechazo no se pueden abandonar.

Francisco Hernández Quiroz

∞

Definiremos una relación entre configuraciones. Sean

∈ Γ.

el símbolo de inicio de la cinta

, n),

donde q ∈ Q, α ∈ Γ yn ∈ N. La configuración inicial es

un alfabeto de cinta, con Σ ⊆ Γ;

el símbolo de espacio en blanco

∞

Autómatas y Lenguajes Formales

Máquinas de Turing

α[n/x]
5 / 46

Francisco Hernández Quiroz

Autómatas y Lenguajes Formales

Máquinas de Turing Indecidibilidad Incomputabilidad

6 / 46

Máquinas de Turing Indecidibilidad Incomputabilidad

Definición y ejemplos...