Máquina de Turing inequívoca

En informática teórica , una máquina de Turing no ambigua es un modelo teórico de computación cuya potencia (bajo restricciones de recursos ) se sitúa entre la de las máquinas de Turing ordinarias y las no deterministas . Una máquina de Turing no ambigua se define como una máquina de Turing no determinista con la propiedad de que, para cada entrada, existe como máximo una ruta de computación que la acepta. ^{[ 1 ]}

Definición formal

Una máquina de Turing no determinista se representa formalmente mediante una 6-tupla , $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ , como se explica en el artículo enlazado anteriormente. ^{[ 2 ]}^{: 178}

Una máquina de Turing inequívoca es una máquina de Turing no determinista. $M$ de tal manera que para cualquier entrada $w$ , $M$ tiene como máximo un cálculo de aceptación en $w$ . ^{[ 1 ]} Es decir, para cada entrada $w$ Existe como máximo una secuencia de configuraciones. $c_{0},c_{1},\ldots ,c_{m}$ con las siguientes condiciones:

$c_{0}$ es la configuración inicial con entrada $w$

$c_{i+1}$ es un sucesor de $c_{i}$ y

$c_{m}$ es una configuración de aceptación. ^{[ 2 ]}^{: 168–169}

Expresividad

El lenguaje de una máquina de Turing no ambigua se define como el mismo lenguaje que acepta la máquina de Turing no determinista. Un lenguaje de cadenas L puede definirse como reconocible sin ambigüedad si es reconocible por una máquina de Turing no ambigua.

La clase de lenguajes reconocibles sin ambigüedad es exactamente la misma que la clase de lenguajes recursivamente enumerables (RE). De hecho, toda máquina de Turing determinista es una máquina de Turing sin ambigüedad, ya que para cada entrada existe exactamente un cálculo posible. Por lo tanto, todos los lenguajes recursivamente enumerables son reconocibles sin ambigüedad. A la inversa, todo lenguaje reconocible sin ambigüedad es reconocible por una máquina de Turing no determinista y, por consiguiente, es recursivamente enumerable.

La clase de complejidad UP se define como la clase de lenguajes que pueden ser decididos en tiempo polinomial por una máquina de Turing no ambigua.

Referencias

1 2 Valiant, Leslie (mayo de 1976). "Complejidad relativa de la verificación y evaluación". Information Processing Letters . 5 (1): 20– 23. doi : 10.1016/0020-0190(76)90097-1 .
1 2 Sipser, Michael (1996-12-01). Introducción a la teoría de la computación (1.ª ed.). International Thomson Publishing. ISBN 978-0-534-94728-6.

Lane A. Hemaspaandra y Jorg Rothe, Computación sin ambigüedad: jerarquías booleanas y conjuntos Turing-completos dispersos , SIAM J. Comput. , 26(3), 634–653

[LeslieValiantIntroduction-1] 1 2 Valiant, Leslie (mayo de 1976). "Complejidad relativa de la verificación y evaluación". Information Processing Letters . 5 (1): 20– 23. doi : 10.1016/0020-0190(76)90097-1 .

[Sipser-2] 1 2 Sipser, Michael (1996-12-01). Introducción a la teoría de la computación (1.ª ed.). International Thomson Publishing. ISBN 978-0-534-94728-6.

[ 1 ]

[ 2 ]