Maquina de Turing

Máquina de Turing

Definiciones previas
Definición. Alfabeto: Diremos que un conjunto finito Σ es un alfabeto
si Σ ≠ ∅ y (∀x)(x ∈ Σ → x es un símbolo indivisible)
Ejemplos

Σ ={a,b}, Σ={0,1}, Σ ={a,b,…z} son alfabetos
Σ ={0,1,00,01} Σ ={sa,ca,casa} no lo son

Definiciones previas
Definicion. Palabra: Se dice que w es una palabra
(cadena o string) sobre Σ si w es una secuenciafinita de
símbolos de Σ
Ejemplos: si Σ ={0,1}, entonces:
0011, 101, 1 son palabras sobre Σ

Definiciones previas
Definicion. Longitud de una palabra: Se denota |w|, es
el número de símbolos quecontiene w.
Por ejemplo: |perro|=5 |010|=3
Nota: notaremos con Σ* al conjunto de todas las palabras
formadas por símbolos de Σ incluída la cadena nula (o
vacía) que tiene longitud cero y denotaremoscon
λ. (| λ | = 0)
Ejemplo:
Σ = {a,b}
Σ* = {λ,a,b,aa,ab,ba,bb,aaa…}

Definiciones previas
Concatenación: La notación utilizada para denotar la
concatenación de dos palabras w y v es w.v
(osimplemente wv).
La concatenación es asociativa pero no conmutativa:
(v.w).x = v.(wx)
v.w ≠ w.v
Se cumple que:
|v.w|=|v|+|w|
La cadena vacía es el elemento neutro para la
concatenacion λ.w = w.λ= w

Definiciones previas
Definición. Sea una cadena w ∈ Σ y un número
natural i, se define la potencia i-ésima de w
como:
w0 = λ
w(i+1) = w.w i

Ejemplo: si w = ab, w3 = ababab

(∀i) (i≥ 0 )

Definiciones previas
Definición. Se denomina lenguaje definido
sobre Σ a cualquier subconjunto de Σ*
Ejemplo: si Σ = {0,1}
∅
Σ*
{λ}
{w ∈ Σ* / w comienza con 1}
{1w0 / w ∈ Σ* }
Sonlenguajes sobre Σ

Características del proceso de
cálculo de una persona
•
•
•

•
•

Se concentra en una porción restringida del
papel
Trabaja con un número finito de símbolos
Puedecambiar la sección de papel en que se
concentra (de acuerdo al símbolo que observa
y a sus estado mental)
Pasa por un número finito de estados
mentales distinguibles
Se asume que siempre contará...