Reducibilidad

PRESENTAN: OSORIO CRUZ ESMERALDA, BORJAS MARTINEZ JESUS BENITO, HERNANDEZ HERNANDEZ ANDRES Y CARBALLO DE LA CRUZ CARLOS

UNIDAD 6 REDUCIBILIDAD


Se dice que un problema L1 se reduce en tiempo polinomial determinístico a otro problema L2, si asumiendo que existe un algoritmo A2 en P que resuelve L2 es posible construir un algoritmo A1 en P que resuelva L1.
Escribiremos L1 W L2 para significar que L1 se reduce a L2.
Intuitiva. Un problema P1 se reduce produce polinomialmente a otro problema P2, si existe un algoritmo que transforme una instancia del problema P1 en una instancia del problema P2 en tiempo polinomial determinístico.
Como podemos apreciar la reducibilidad no es más que utilizar dos problemas uniéndolos para así poder optimizar polinomialmente el rendimiento de los mismos.
Ya teniendo una idea más clara a lo que se refiere a la reducibilidad podemos adentrarnos en lo que son los problemas insolubles ya que al tener un problema insoluble podremos aplicar la reducibilidad para convertirlo en soluble.
Estrategia de demostración por reducibilidad
Para demostrar que un problema es insoluble:
1. Suponer que el problema es soluble.
2. Tomar un problema que ya se conozca, o pueda demostrarse, insoluble, para plantear la reducción.
3. Es importante recordar que debe reducirse el problema elegido en el punto 2 al problema que supusimos soluble (demostración por el absurdo)
4. Demostrar la reducción.
No olvidar la conclusión de la demostración.

6.1 Problemas insolubles para la teoría de lenguajes

Como será lógico para algunos al decir que un problema es insoluble se infiere que es un problema que nuestro autómata no puede resolver.
Se tiene un problema cuando se desea encontrar uno o varios objetos desconocidos que cumplen condiciones y/o relaciones, previamente definidas, respecto a uno o varios objetos conocidos.

TIEMPO POLINOMICO
En computación cuando el tiempo de ejecución de un algoritmo es menor que un cierto valor calculado a partir del número de variables implicadas usando una formula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.

CLASIFICACION DE PROBLEMAS

Los problemas se clasifican por la existencia de una solución en solubles, no solubles e indecidibles.
Un problema se dice soluble si se sabe de antemano que existe una solución para él.
A su vez, los problemas solubles se dividen en dos clases: los algorítmicos y los no algorítmicos.
Un problema se dice algorítmico si existe un algoritmo que permita darle solución.
Un problema se dice no algorítmico si no existe un algoritmo que permita encontrar su solución.

Un problema se dice insoluble si se sabe que no existe una solución para él.
Un problema se dice indecidible si no se sabe si existe o no existe solución para él.
Ejemplo:
Un robot puede apilar en ciertos lugares cajas e diferentes tamaños. La caja a apilar no puede ser más grande que as que ya estén apiladas en dicho lugar. El robot puede solo tomar la caja de más arriba de una pila. ¿Cómo puede el robot pasar las tres cajas apiladas en el lugar A al lugar C usando si es necesario el lugar de apilar B?


6.2 Un Problema Simple Insoluble

1.- Una partícula se mueve en el espacio de manera aleatoria, si en el instante de tiempo t se encuentra en la posición x, ¿Cuál será la posición exacta de dicha partícula 10 segundos después?

Objeto desconocido. Una posición
Objetos conocidos. Posición en el instante de tiempo t.
Condiciones. La partícula se mueve en el espacio de manera aleatoria
Tipo de problema. Insoluble. Debido a que no existe forma de predecir la posición de la partícula, pues se mueve de manera aleatoria.

2.- Problema de la Detención de MT

Un problema de decisión de especial importancia es el “problema de detención de la máquina de Turing” (Halting Problem)

Dada una MT T y una cadena α, ¿existe un algoritmo para decidir si T se detendrá comenzando en el estado inicial con α en la cinta?

Alan Turing, a fines de 1930, enunció y demostró que este problema es insoluble.

Teorema: El problema de la detención de la máquina de Turing no es algorítmicamente soluble.
Resultados auxiliares a utilizar:
Si L es recursivo, entonces su complemento también lo es
Problema de la Detención de MT

Algoritmo Detención MT
Dato de Entrada: T, α
Dato de Salida: Estado
Comienzo
.....
Devolver Estado con valor
“se detiene” o “cicla”
Fin

6.3 FUNCIONES COMPUTABLES

Consisten en las funciones que pueden ser calculadas por una maquina de turing.
Las funciones computables son usadas para discutir computabilidad sin referirse a ningún modelo de computación concreto, como máquina de Turing o máquina de registros.
En este apartado, se pueden utilizar los axiomas de Blum para definir una teoría de complejidad computacional sobre el conjunto de las funciones computables. Según la tesis Church-Turing, la clase de las funciones computables es equivalente a la clase de las funciones definidas por funciones recursivas, calculo de λ (lambda), o algoritmos de Markov.
Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una maquinan de turing, una maquina de post, o una maquina de registros.
En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable se conoce como un problema de funciones.
Definen usando como principales operaciones la recursión y composición de funciones forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables.
Una función parcial.
f:⊆ N → N
se llama computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro normalmente se escribe P¹ o P.
una función total
f: N → N
se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro se escribe normalmente R¹ o R .
Una función computable f se llama predicado computable si los valores de la función son booleanos, o sea
f: N → {0,1}
la teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una maquina de turing.
El objetivo es concretar la noción de función calculable, esto quiere decir, una función/expresión cuyos valores se pueden calcular de forma automática a partir de un algoritmo. Surge así una teoría que producirá resultados positivos y negativos.


6.4 Reducibilidad de Turing

En la teoría de la computabilidad, una reducción de Turing de un problema de la A a la B de un problema puede ser entendida como un algoritmo que se podría utilizar para resolver un caso que tenía a su disposición una subrutina para resolver b, pero la definición más formalmente es una reducción Turing es juna función computable por una maquina oráculo con un oráculo para B. reducciones de Turing se puede aplicar tanto a los problemas de decisión y problemas en la función.

Máquina oráculo

Una maquina oráculo es una maquina Turing conectado a un oráculo. El oráculo, en este contexto, se considera como una entidad capaz de responder a alguna colección de preguntas, y por lo general representan como un cierto subconjunto de los números naturales.
Entonces la maquina oráculo puede realizar todas las operaciones habituales de una maquina de Turing, y también puede consultar el oráculo de una respuesta a una pregunta concreta de la forma “es x de A?”.

Una maquina oráculo, como una máquina de turing incluyen:

• Una cinta de trabajo: una secuencia de células sin principio ni fin, cada uno de los cuales puede contener una B (de blanco) o un 1.
• Una cabeza de lectura/escritura: se basa en una sola celda de la cinta de trabajo y puede leer los datos, escribir nuevos datos, y mover hacia la izquierda o la derecha a lo largo de la cinta.
• Un mecanismo de control: que puede estar en uno de un número finito de estados, y que llevara a cabo diferentes acciones (los datos de lectura y escritura de datos, moviendo el mecanismo de control, y el cambio de estados) en función del estado actual y los datos que se leen.
• Una cinta de oráculo: en la que se imprime una secuencia finita de B y 1, correspondiente a la función característica del oráculo conjunto A.
• Una cabeza de oráculo: que como la cabeza de lectura y escritura puede moverse a la izquierda o a la derecha o a lo largo de la cinta de lectura de datos del Oráculo, pero que no puede escribir.

las diferencias importantes entre la reducción M y la de Turing son obviamente el poder efectuar mas de una pregunta, y en segundo lugar el poder “hacer lo contrario” de lo que indica la respuesta; pero la propiedad realmente relevante resulta ser un poder que cada pregunta dependa esencialmete de las respuestas obtenidas a preguntas anteriores (“adaptabilidad” de la reducción).

ORACULOS Y PROBLEMAS DE LA PARADA

Es posible postular la existencia de un oráculo que calcula una función no computable, como la respuesta al problema de la parada o algo equivalente. Una maquina con un oráculo de este tipo es una hypercomputadora,
La paradoja de parada todavía se aplica a estas maquinas, es decir, a pesar de que puede determinar si determinadas maquinas de Turing se detienen ante determinadas entradas, no pueden determinar si las maquinas con oráculos de parada equivalentes si se detienen.
Este hecho crea una jerarquía de las maquinas, llamada la jerarquía aritmética, cada uno con un oráculo de parada más potente y un problema aun mas difícil de detener.
Relación de Turing completo a la universalidad computacional.
Como ya se ha definido anteriormente, se corresponde solo parcialmente a la integridad de Turing en el sentido de la universalidad computacional. En concreto, una maquina de Turing es una maquina universal de Turing si y solo si su problema de parada (es decir, el conjunto de insumos para que con el tiempo se detiene) es uno de muchos completa. Por lo tanto, una condición necesaria pero no suficiente para que una maquina sea computacionalmente universal, que es detener el problema de la maquina que Turing completo para el conjunto X recursivamente enumerable de conjuntos.

Bibliografía

 Título del libro: Introducción a las Ciencias de la Computación.
Autor: J. Glenn Brookshear.
Cuarta edición.
 Título del libro: TEORIA DE LA COMPUTACION, Lenguajes Formales, Autómatas y complejidad.
Autor: J. Glenn Brookshear
Primera edición 1993
 “Teoría de la Computabilidad – Transparencias de Clase”. © Dr. Chesñevar, Mg. Cobo, Dr. Martínez - Universidad Nacional del Sur 2002- 2009

 http://sistemas.itlp.edu.mx/tutoriales/teoriadelacomputacion/index.htm

Reducibilidad

5.2 PROBLEMAS DE HALTING ( POR JOSE LUIS - ENRIQUE - CARLOS ABDEL)

5.2.- El problema de Halting

El problema de Halting o de paro consiste en determinar si una máquina de Turing cualquiera se detendrá ante cualquier entrada dada.

Es decir, si existe una máquina MTh capaz de determinar si cualquier otra máquina se va a detener o no. Es conocido que el problema del alto es indecidible.

Básicamente, Turing definió las bases de las computadoras modernas y planteo un problema sobre ellas, llegando a la conclusión de que no hay ningún algoritmo que lo resuelva. Es el problema de la detención (problema de Halting); el problema de saber si un problema se cuelga cuando corre en la computadora. Turing demostró que el problema de la detención es indecidible, es decir, demostró que había problemas que una maquina no podía resolver.

El problema de la parada o problema de la detención para máquinas de Turing es el ejemplo de problema irresoluble más conocido. Consiste en determinar si una máquina de Turing se detendrá con cierta entrada, o bien quedará en un ciclo infinito. Este fue el primer problema que se demostró formalmente que no tenía solución.

El concepto de problema indecidible o irresoluble se aplica a problemas de decisión, es decir, problemas a los que podemos decir si tienen solución o no. Dentro de estos problemas, existe un conjunto al que no le podemos asignar una respuesta, ni afirmativa ni negativa: no existe un algoritmo que nos permita determinar si el problema tiene solución.

Una de las razones por la que es importante conocer que el problema de la parada no tiene solución, es que nos permite decidir si otros problemas son resolubles o no. El razonamiento a seguir sería: si suponiendo que un problema es decidible, podemos demostrar que el problema de la parada tiene solución, entonces podemos llegar a la conclusión de que el problema en cuestión no la tiene, por reducción al absurdo.

* El método de la Diagonalización

La prueba de la indecidibilidad del problema de Halting utiliza una técnica llamada diagonalización, descubierta por el matemático Georg Cantor en 1873. Cantor estaba interesado con el problema de medir los tamaños de los conjuntos infinitos.

Si tenemos dos conjuntos infinitos, ¿cómo podemos decir si uno es más grande que el otro o si son del mismo tamaño? Para conjuntos finitos, por supuesto, responder a estas preguntas es fácil. Nosotros simplemente contamos los elementos de un conjunto finito, y el número resultante es su tamaño.

Pero, si tratamos de contar los elementos de un conjunto infinito, ¡nunca terminaríamos! Así que no podemos utilizar el método de conteo para determinar los tamaños relativos de los conjuntos infinitos.

Aquí dejo un link donde encontré un ejercicio con su respectiva explicación.

http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf

BIBLIOGRAFIA.

http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf

http://www.glyc.dc.uba.ar/santiago/charlas/SdC06.pdf

http://es.wikipedia.org/wiki/Problema_de_la_parada

4.5 PROBLEMAS DE HILBERT

4.5. PROBLEMAS DE HILBERT

David hilbert Matematico aleman nacio el 23 de enero de 1982 en koïngsberg rusia y murio el 14 de febrero de 1943

El 8 de Agosto de 1900, en París, un profesor de la Universidad de Göttingen dio una conferencia que capturaría la imaginación de los matemáticos del siglo XX. El profesor era David Hilbert y su plática se tituló simplemente “Problemas Matemáticos”.

Hilbert presentó diez de los problemas (1, 2, 6, 7, 8, 13, 16, 19, 21 Y 22) en la conferencia, La lista completa se publicó más adelante.

Fue así que propuso una lista de 23 problemas, no como un reto, sino como un incentivo para los matemáticos del nuevo siglo. Esta lista es conocida como “Los Problemas de Hilbert” y consta de problemas importantes en Teoría de Números, Álgebra, Geometría, Análisis, Teoría de Conjuntos y Fundamentos Axiomáticos.

En este momento, de los 23 problemas, 16 se consideran básicamente resueltos, 4 son más programas de trabajo que problemas concretos, y 3 permanecen sin resolver problemas 3, 7, 10, 11, 13, 14, 17 , 19 Y 20 tienen una solución aceptada por consenso.

Por otro lado, los problemas 1, 2, 5, 9, 15, 18, 21 Y 22 tienen soluciones de aceptación parcial, pero existe cierta controversia al respecto de si la solución resuelve realmente el problema.

1er
La hipótesis del continuo (esto es, no existe conjunto cuyo tamaño esté estrictamente entre el de los enteros y el de los números reales)

Se ha probado la imposibilidad de probarlo como cierto o falso mediante los axiomas de Zermelo-Fraenkel. No hay consenso al respecto de considerar esto como solución al problema.1

2º
Probar que los axiomas de la aritmética son consistentes (esto es, que la aritmética es un sistema formal que no supone una contradicción).

Parcialmente resuelto: hay quienes sostienen que se ha demostrado imposible de establecer en un sistema consistente, finitista y axiomáticos Sin embargo, Gentzen probó en 1936 que la consistencia de la aritmética se deriva del buen fundamento del ordinal, un hecho sujeto a la intuición combinatoria.

3er
Dados dos poliedros de igual volumen, ¿es siempre posible cortar el primero en una cantidad finita de piezas poliédricas que puedan ser ensambladas de modo que quede armado el segundo? Resuelto. Resultado: no, probado usando invariantes de Dehn

4º
Construir todas las métricas cuyas rectas sean geodésicas.
Demasiado vago para decidir si se ha resuelto o no.

5º
¿Son los grupos continuos grupos diferenciales de forma automática?
Resuelto por Andrew Gleason (1952)

6º
Axiomatizar toda la física
* La mecánica clásica: Hamel (1903).
* La termodinámica: Carathéodory (1909).
* La relatividad especial: Robb (1914) y Caratheodory (1924) independientemente.
* La teoría de probabilidades: Kolmogórov (1930).
* La teoría cuántica de campos: Wightman a finales de los años 1950.

7º
¿Es a b trascendental, siendo a ≠ 0,1 algebraico y birracional algebraico?
Resuelto. Resultado: sí, ilustrado por el teorema de Gelfond o el teorema de Gelfond-Schneider

8º
La hipótesis de Riemann (la parte real de cualquier cero no trivial de la función zeta de Riemann es ½) y la conjetura de Goldbach (cada número par mayor que 2 se puede escribir como la suma de dos números primos).
Abierto.4

9º
Encontrar la ley más general del teorema de reciprocidad en cualquier cuerpo numérico algebraico
Parcialmente resueltos

10º
Encontrar un algoritmo que determine si una ecuación diofántica polinómica dada con coeficientes enteros tiene solución entera. Resuelto. Resultado: no, el teorema de Matiyasevich (1970) implica que no existe tal algoritmo.

11º
Resolver las formas cuadráticas con coeficientes numéricos algebraicos. Parcialmente resuelto:
* Sobre los números racionales: Hasse (1923-1924).
* Sobre los números enteros: Siegel en los años 1930

12º
Extender el teorema de Kronecker sobre extensiones abelianas de los números racionales a cualquier cuerpo numérico de base.
Abierto

13º
Resolver todas las ecuaciones de 7º grado usando funciones de dos parámetros.
Resuelto negativamente por Vladímir Arnold y Andréi Kolmogórov en 1957.

14º
Probar la finitud de ciertos sistemas completos de funciones.
Resultado: no, en general, debido a un contra ejemplo, Nagata(1962).

15º
Fundamento riguroso del cálculo enumerativo de Schubert.
Parcialmente resuelto, Van der Waerden a finales de los años 1930.

16º
Topología de las curvas y superficies algebraicas. Abierto

17º
Expresión de una función definida racional como cociente de sumas de cuadrados
Resuelto. Resultado: se estableció un límite superior para el número de términos cuadrados necesarios, Pfister (1967). La solución negativa en general se debe a Du Bois (1967).

18º
¿Existe un poliedro irregular y que construya otros poliedros? ¿Cual es el apilamiento compacto más denso?
Resuelto6

19º
¿Son siempre analíticas las soluciones de losLagrangianos?
Resuelto por Bernstein (1904). Resultado: sí

20º
¿Tienen solución todos los problemas variacionalescon ciertas condiciones de contorno?
Resuelto. Ha supuesto un área importante de investigación durante el siglo XX, culminando con las soluciones al caso no lineal.

21er
Probar la existencia de ecuaciones lineales diferenciales que tengan un grupo monodrómico prescrito
Resuelto. Resultado: sí o no, dependiendo de una formulación más exacta del problema. Según Gray resuelto de forma negativa por Anosov y Bolibruch(1994).

22º
Uniformización de las relaciones analíticas por medio de funciones automórficas
Resuelto por Koebe (1907) y Poincaré independientemente (1907).

23er
Extensión de los métodos del cálculo de variaciones
Resuelto
INTEGRANTES:
CODALLOS MOGOLLON MARTHA ANGELICA
RUIZ SALAS JUANA
MARTINEZ MAR FILIBERTO

Bibliografía;
[1] Arnold, V.I. et. al. Mathematics: Frontiers and Perspectives. IMU and AMS (2000).
[2] Hilbert, David. “Mathematical Problems”. Bulletin AMS 8 (1902), 437-479.
[3] Reid, Constance. Hilbert. Springer-Verlag (1970).
[4] Smale, S. “Mathematical Problems for the Next Century”. Mathematical Intelligencer.
20:2 (1998), 7-15.
[5] Yandell, B. H. The Honors Class. A. K. Peters, Ltd. (2002).

4.2 CONSTRUCCIÓN MODULAR DE UNA MÁQUINA DE TURING

Mediante esta Técnica se pueden desarrollar maquinas de Turing complejas a partir de Bloques y apartir de maquinas mas pequeñas mediante diagramas de transiciones.

COMBINACIÓN DE MAQUINAS DE TURING

La construcción de maquinas de Turing se lleva a cavo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.

Suponga que tenemos dos máquinas de Turing M1 y M2, con diagramas de tranciciones T1 y T2, respectivamente, y simbolos de cinta del conjunto . Si queremos desarrollar un diagrama de transiciones para otra máquina que simule las actividades de M1 seguidas por las de M2, bastaría con eliminar la designación de parada del estado de parada T1 y la caracteristica de inicio del estado inicial de T2, y luego dibujar un arco con etiqueta x/x para cada x en , del antiguo estado d eparada de T1 al antiguo estado inicial de T2.

(Este aprtado puede ser el deceado pero tiene desventajas)... Supongamos que queremos que la amquina compuesta se detenga después de simular M1, a menos que el símbolo actual, al llegar al estado de parada, sea z, en cuyo caso nos gustaria que la nueva máquina simulara las acciones de M2; o supongamos que necesitamos combinar 3 diagramas y controlar el paso de uno aotro dependiendo del valor del símbolo actual al llegar a cada uno de los antiguos estados de parada. En este caso re requiere un enlace mas complicado.

Si necesitamos combinar los diagramas de transiciones de varias máquinas que simule alguna combinación de las máquinas originales. Seguimos los siguientes pasos:

1. 
   
   Elimine la característica de inicio de los estados iniciales de todas las máquinas, excepto la de aquél donde iniciará la máquina compuesta.


2. 
   
   Elimine la caracyerística de detención de los estados de parada de todas las máquinas e introduzca un nuevo estado de parada que no se encuentre en ninguno de los diagramas que se combinan.


3. 
   
   Para cada uno de los antiguos estados de parada p y cada x en , dibuje un arco de la siguiente forma:

a).- Si la máquina compuesta debe detenerse al llegar a p con el símbolo actual x, dibuje un arco con etiqueta x/x de p al nuevo estado de parada.

b).- Si al llegar al estado p con el símbolo actual x, la máquina compuesta debe transferir el control a la máquina , dibuje entonces un arco con etiqueta x/z de p al estado q de M, donde .

Mueve la cabeza una celda hacia la derecha.

Encuentra la primera x ala derecha de la celda actual

Encuentra la primera y a la derecha de la celda actual

Encuentra la segunda ocurrencia del símbolo distinto de espacio en blanco que está a la derecha de la posición inicial de la cabeza

La Maquina compuesta de las figuras anteriores podria resumirse con el diagrama compuesto:

donde el nodo A representa la máquina que mueve su cabeza una celda a la derecha, B la máquina que busca una x y C la máquina que busca una y.

• Ejemplo de Maquinas de Turing compuesta:

• Otra abreviatura que utilizaremos consiste en aplicar la notacion:

........INTEGRANTES DEL EQUIPO.....

Martinez Martinez Tomas Alejandro

Marquez del Angel Yaznhara

Perdomo Sanchez Lizeth

Cruz Hernandez Ivan

Direccion del Wiki

Aqui les dejo la direcciòn del wiki, en donde subiran sus archivos: http://teoriaitca.wikispaces.com

En los correos que me dieron ya envie la invitaciòn para que se unan. Si faltan direcciones, ustedes hagan la solicitud para unirse y yo los aceptare.

4.4 Variantes de una maquina de turing

4.- VARIANTES DE UNA MAQUINA DE TURING

Una máquina de Turing puede hacer cualquier cosa que pueda hacer una computadora real y aún cuando una MT no puede resolver ciertos problemas, estos problemas están más allá del los límites teóricos de la computación; es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles. La MT consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

Avanzar el cabezal lector/escritor para la derecha.

Avanzar el cabezal lector/escritor para la izquierda.

Una máquina de Turing es una tupla de 7 elementos (Q, Σ, Γ, δ, qo, qa(aceptar), qr (rechazar)), donde:

Q, Σ, Γ son conjuntos finitos.

1. Q es el conjunto de estados

2. Σ es el alfabeto de entrada

3. Γ es el alfabeto de la cinta

4. δ: Q x Γ → Q x Γ x { L, R }

5. qo Є Q es el estado inicial

6. qa Є Q es el estado de aceptación

7. qr Є Q es el estado de rechazo, donde qa ≠ qr.

Según va computando una MT, ocurren cambios en el estado actual, el contenido de la cinta y la posición de la cabeza de la cinta. Una combinación de estos tres elementos se llama una configuración de la máquina de Turing. La idea subyacente en el concepto de máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente enumérables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.

Existen muchas alternativas de la máquina de Turing, incluyendo cintas múltiples o indeterminismo. Estas son llamadas variantes del modelo de la máquina de Turing. Tanto el modelo original como sus variantes tienen el mismo poder, es decir, reconocen la misma clase de lenguajes. Para ilustrar la robustez del modelo de la máquina de Turing, hagamos una variación de la función de transición permitida. En la definición original, la función de transición fuerza a la cabeza de la cinta a moverse a la izquierda o a la derecha después de cada paso, la cabeza de la cinta no puede permanecer sin movimiento. Supongamos que le damos a la máquina de Turing la habilidad para que la cabeza de la cinta permanezca sin movimiento. La función de transición tendría la forma δ: Q x Γ → Q x Γ x { L, R, S }.

Los tipos de variantes de una maquina de Turing

Máquina de Turing indeterminista

Una máquina de Turing indeterminista se define de la forma esperada. En cada punto en una computación la máquina puede proceder de acuerdo a varias posibilidades. La función de transición para una máquina de Turing indeterminista tiene la forma

δ: Q x Γ → P(Q x Γ x { L, R })

En general, un cálculo , en una máquina no determinista, es un árbol de descripciones instantáneas (DI), en lugar de ser una secuencia lineal de DI, que es el caso de las máquinas deterministas. En el ejemplo, el árbol de DI es binario. De él representamos solo los dos itinerarios correspondientes a las funciones arriba indicadas:

.... b 1 1 ... 1 b ... s₀

_{/ \}

_{/ \}

s₀ b 1 1 ... 1 b b 1 1 ... 1 b s₂

/ \

-------------- b 1 b 1 ...1 b s₂

-------------- ----------------

s₀ b 1 1 ... 1 b b 1 b ... 1 b s₂

s₀ b 1 1 ... 1 b b 1 b ... b b s₂

s₁ b 1 1 ... 1 1 b

Otros itinerarios corresponden al cálculo de f (x) = 2, 3, etc…

Pero en general, puede ser un árbol cualquiera. Si la máquina está bien construida, para un ejemplar (instance), cada itinerario del árbol conduce a un resultado en general diferente del de los demás itinerarios. Con esta perspectiva uno se puede preguntar si el indeterminismo posibilita el cálculo de funciones que no pueden ser calculadas con máquinas deterministas. La respuesta es NO, porque una función calculable asigna un valor (único) del rango a cada n-upla (entrada) del dominio para la que exista solución. Cada itinerario de una máquina indeterminista corresponde al cálculo de una determinista. En AF y AP es clara la utilidad que tiene construir autómatas finitos no deterministas para facilitar la construcción de los autómatas deterministas correspondientes. Igualmente el concepto es útil en MT.

Cuando la MTND procesa un ejemplar para el que la función está indefinida, se produce un árbol de cálculos que no tiene ninguna hoja con parada por función calculada; es decir, todas las paradas son de función indefinida, o bien no hay parada (cálculo infinito). Pero una máquina no determinista puede ser siempre sustituida por la máquina determinista equivalente con dos paradas, una para función calculada y otra para función indefinida. En la práctica, lo que conviene es detectar las entradas para las cuales la M T no pararía (función parcialmente calculable).

Ejemplo:

Cada máquina de Turing indeterminista tiene una máquina de Turing ordinaria (determinista) equivalente.

1. Si L es reconocido por una MTD, L es reconocido por una Máquina de Turing No Determınista. Las máquinas de Turing deterministas son máquinas de Turing no deterministas en las que solo hay una transición por cada par estado/sımbolo.
2. Si L es reconocido por una MT No Determinista, L es reconocido por una MTD.
Sea MN que acepta L(MN) entonces mostramos que existe M’ que acepta L(M0c=3).
L(MN) = L(M0c=3) y L(M0 : c = 3) = L(M0c=1)
Podemos simular una MTND con una MT determinsta de tres cintas:
1. Se obtiene un n que es el número máximo de transiciones en los conjuntos δ(q, a).
2. En la primera cinta va la cadena de entrada. 3. En la segunda cinta se generan las cadenas sobre el alfabeto 1, 2, ..., n por orden numerico.

Una modificación importante que se puede introducir en nuestra definición original es la eliminación del requerimiento de que la regla de transición sea una función. Esta máquina de Turing se llamára máquina de Turing no determinista, ya que para un estado actual y el símbolo actual de la cinta, puede haber un numero finito de movimientos a elegir. Por tanto, la regla de transición, Δ, de dicha máquina, satisface: Δq, σ⊆ Q ×Γ×{L, R}

Por ejemplo, si la máquina de Turing tiene una transición

Δq, a={(q1, b, R), (q2, a, L)} Entonces los movimientos (q1, abbab) (q1, abbbb) y (q1, abbab) (q2, abbab) Son posibles.

Ya que cualquier máquina de Turing determinista es también no determinista, es lógico que una máquina de Turing determinista se puede simular mediante una no determinista. También una máquina de Turing determinista puede simular una no determinista. Por tanto, no se gana ninguna potencia adicional a causa del no determinismo.

Para ver como se realizaría la simulación, sea M1 una máquina de Turing no determinista que acepta algún lenguaje. Describiremos una máquina de Turing (determinista) M2, que será de tres cintas, que simule M1. Téngase en cuenta que, para cualesquiera estado actual y símbolo de la cinta de M1, hay un número finito de movimientos para realizar a continuación. Numeraremos dichos movimientos 1, 2,…, k. Puesto que tanto Q1 como 1 de M1 son conjuntos finitos, solo existirá un número finito de pares de estado actual y símbolo de la cinta. Por tanto, se puede obtener el par que tenga el mayor número de posibles movimientos a realizar a continuación. Sea este número n. Entonces cualquier computación para M1 se puede representar mediante una secuencia finita de números elegidos entre 1 y n, donde cada número representara el movimiento elegido para ser realizado a continuación en esta etapa de la computación. No toda secuencia finita de número entre 1 y n representan computaciones validas puesto que puede que haya menos de n elecciones para algún par estado-símbolo de la cinta.

En la máquina de Turing de tres cintas, M2, la primera cinta almacenara la entrada y la segunda generará, de forma sistemática, secuencias finitas de números entre 1 y n. Para cada secuencia, M2 copiará la cadena de entrada en la tercera cinta y simulará M1 sobre esta cinta usando la secuencia almacenada en la segunda cinta como guía para realizar la computación. Si una de las secuencias elegidas hace que M1 acepte la cadena, entonces dicha secuencia será generada por M2 y la cadena será aceptada. Si ninguna de las secuencias elegidas provoca la aceptación por parte de M1 entonces tampoco M2 la aceptará. Obsérvese que este razonamiento se redacta en términos de la aceptación de lenguajes. Las máquinas de Turing no deterministas se interpretan como aceptadores de lenguajes. Además se puede generalizar este razonamiento fácilmente, para simular una máquina de Turing multicinta no determinista. En esta sección hemos descrito varias modificaciones a realizar sobre nuestra máquina de Turing original, ninguna de las cuales tiene mayor o menor potencia que la original. Entonces, cabe preguntarse por qué nos hemos molestado en estudiarlas si ninguna de ellas aporta ninguna ganancia en cuanto a capacidad computacional, o por qué no nos hemos centrado en la más sencilla de todas ellas. Una de las razones es que, a partir de ahora, conocemos formas distintas de resolver problemas mediante las máquinas de Turing. Si una de ellas resolviera un problema, de forma más fácil que la original entonces, sin temor a perder generalidad, usaremos dicha variante. Otra razón aun más profunda para el estudio de dichas modificaciones y sus equivalencias con el original, es que con esto se comprende aun más la actualidad de las máquinas de Turing. Cualquier computación que se pueda realizar por medio de una de las nuevas máquinas cae dentro de la categoría de “computable por una máquina de Turing” y, por tanto, es mecánicamente computable.

Maquina de turing con cinta mutipista

Es aquella que mediante la cual cada celda de la cinta de una màquina sencilla se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas; se dice que esta cinta tiene mutiples pistas puesto que cada celda de esta MT contiene mùltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. los movimientos que realice esta esta màquina dependeràn de sus estado actual y de la n-tupla que represente el contenido de la celda actual, se podria decir que posee un solo cabezal al igual que una MT sencilla. En el modelo multi-pista, la cinta està dividida en un número finito k de pistas. La funciòn de transicion adquiere la siguiente forma:
δ: Q x Γk → Q x Γk x {D, I, N}
δ(q, (a1, a2, a3, ..., ak)) = (p, (b1, b2, b3, ..., bk), {I,D,N})
Donde los ai y los bi son sìmbolos de Γ.

Las Màquinas de Turing que actùan sobre cinta dividida en k pistas aceptan los mismos lenguajes que las MT estándares.

Es decir el nuevo alfabeto de cinta para k-uplas (s1, s2, ..., sk) es el producto cartesiano Γk=
Γ × Γ... × Γ{kV eces}

Ejemplo: Para representar la suma de dos binarios la MT transformarà:

Máquina de Turing multicinta

Una máquina de Turing multicinta es como una máquina ordinaria con muchas cintas. Cada cinta tiene su propia cabeza de la cinta. Inicialmente la cadena de entrada se encuentra en la cinta 1 y las otras cintas están en blanco. La función de transición se modifica para permitir la lectura, escritura y movimiento de todas las cintas simultáneamente. Formalmente, se define como

δ: Q x Γ k → Q x Γ k x {L, R }k, donde k es el número de cintas. La expresión

δ (qi, a1,…, ak) = (qj, b1, …, bk, L, R, …, L)

Significa que, si la máquina se encuentra en el estado qi y las cabezas 1 a la k están leyendo los símbolos a1 hasta ak, la máquina va al estado qj, escribe los símbolos b1 hasta bk y mueve cada cabeza a la izquierda o derecha según se especifica. Pareciera que las máquinas de Turing multicinta son más poderosas que las máquinas de Turing ordinarias, pero podemos mostrar que son equivalentes. Recordemos que dos máquinas son equivalentes si reconocen el mismo lenguaje.

• Cambia de estado dependiendo del estado actual y del contenido de las celdas de todas las cintas, que estan anlizando actualmente las cabezas de lectura/escritura.


• Escriben un nuevo símbolo en cada una de las celdas barridas por su cabezas de lectura/escritura.


• Mueve cada una de sus cabezas hacia la izquierda o hacia la derecha(de forma independiente al resto de las cabezas).

Tambien son conocidas como máquinas con cintas de varias pistas (MTVP), se le puede ver como máquinas de varias cintas con movimientos sincronizados; MT Y MTVP son equivalentes porque reciprocamente, dada una máquina M^k del tipo MTVP con k pistas, la podemos simular con una máquina M del tipo MT de cualquiera de las dos maneras alternativas:

1. Si A es el alfabeto de M^k, entonces en cada momento el funcionamiento de M^k depende de la lista de k simbolos que aparece en la casilla actual, consistente de K casillas, una por cada pista. Esto define a una máquina de tipo MT sobre el alfabeto A^k que es una potencia cartesiana del original.


2. Consideremos una cinta de una sola pista en donde sus casillas se agrupan en bloques de k casillas. la posición j-èsima de la i-èsima pista en la cinta M^k corresponde a la posición ((j-1)*k+i) -èsima de la nueva cinta. En esta nueva casillas contiguas en la misma pista de M^k distanciaràn de K casillas. El mecanismo de funcionamiento se modifica para que cada movimiento de M^k obligue a revisar un bloque de K casillas y haga la modificaciòn correspondiente, trabajando siempre en bloques.

Por tanto, la función de transición para la máquina de Turing con n cintas es de la forma δ : Q X Гⁿ Q X Гⁿ X { L, P}ⁿ donde una transición de la forma δq, σ1, σ2,…, σn=(p,τ1,τ2, …, τn, (X1, X2,…, Xn)) significa que cambia del estado q a p, reemplaza σi por τi en la cinta i y mueve la cabeza de la cinta i en la dirección Xi.
Ejemplo
Construir una MT con dos cintas que acepte el lenguaje L = {aibici i >= 1}
δ(q0, (a,B)) = (q0, (a,X), (D,D))
δ(q0, (b,B)) = (q1, (b,B), (N, I))
δ(q1, (b,X)) = (q1, (b,X), (D, 1))
δ(q1, (c,B)) = (q2, (c,B), (N,D))
δ(q2, (c,X)) = (q2, (c,X), (D,D))
δ(q2(B,B)) = (q3, (B,B), (N,N))

Máquina de Turing Multidimensional

Otra modificación que se puede hacer en nuestra máquina de Turing original es permitir que la cinta tenga muchas dimensiones. Por ejemplo, una cinta de dos dimensiones que se extienda hacia abajo y hacia arriba, al igual que hacia la derecha y hacia la izquierda. Dependiendo del estado actual de la máquina de Turing y del símbolo analizado, cambia de estado, escribe un símbolo en la celda actual y se mueve a la izquierda, a la derecha, hacia arriba o hacia abajo. Por tanto, la función de transición para esta máquina de Turing será de la forma

δ: Q×Γ → Q×Γ×{L,R,U,D}

Una máquina de Turing multidimensional simula, fácilmente, una máquina de Turing estándar. Simplemente realiza todas sus computaciones en una unida dimensión. Una máquina de Turing estándar también puede simular una máquina de Turing multidimensional y, por tanto, la complejidad y flexibilidad adicional que se debe a la múltiple dimensión, no es una capacidad real. Para simular una máquina de Turing de dos dimensiones mediante una máquina de Turing estándar, primero asociaremos una dirección a todas las celdas de la cinta. Una forma de hacerlo es fijar, de forma arbitraria, un lugar en la cinta a partir del cual se asignaran las coordenadas a las celdas de la misma forma que se realiza en el plano de coordenadas. Entonces, se usara una cinta de dos pistas para simular la MT; una pista se encargarà de almacenar el contenido de las celdas y la otra las corrodenadas, utilizando un simbolo (*) para separar los valores de las coordenadas.

Por ejemplo

Entonces, usaremos una cinta de dos pistas para simular la máquina de Turing. Una pista se encargara de almacenar el contenido de las celdas y la otra las coordenadas. Según esto, si la celda (1,2) contiene una a y la celda (-3, 12) contiene una b, la cinta de la máquina de Turing que realiza la simulación será como

a b

1 * 2 * - 3 * 1 2

Obsérvese que se ha introducido un nuevo símbolo para separar los valores de las coordenadas. Para simular un movimiento de una máquina de Turing de dos dimensiones, esta máquina calcula la dirección de la celda a la que se movería la máquina de Turing de dos dimensiones. Entonces, localiza en la pista inferior la celda con dicha dirección y cambia el contenido de la celda en la pista superior.

Enumeradores

Un enumerador es una máquina de Turing con una impresora, la cual puede utilizarse como un dispositivo de salida para imprimir cadenas.

Un enumerador empieza con una cinta de entrada en blanco. Si el enumerador no se detiene, puede imprimir una lista infinita de cadenas. El lenguaje enumerado por E es la colección de todas las cadenas que eventualmente imprime.

Primero mostraremos que si tenemos un enumerador E que enumera un lenguaje A, una MT M reconoce A. La MT M trabaja de la siguiente manera:

M = “Sobre la cadena de entrada w:

1. Ejecutar E. Cada vez que E imprima una cadena, compararla con w.

2. Si w aparece en la salida de E, aceptar. Claramente, M acepta aquellas cadenas que aparecen en la lista de E.

Ahora demostraremos en la otra dirección. Si la MT M reconoce un lenguaje A, podemos construir el siguiente enumerador E para A. Digamos que s₁, s₂, s₃, … es una lista de todas las posibles cadenas en Σ*.

M = “Ignorar la entrada w:

1. Repetir lo siguiente para i = 1, 2, 3, …

2. Ejecutar M para i pasos sobre cada entrada s₁, s₂, … s_i

3.Si cualquier computación acepta, imprimir la s_k correspondiente Si M acepta una cadena particular s, eventualmente aparecerá en la lista generada por E.

Quíntuple.

En una máquina de Turing con transición quíntuple, la función de transición tiene el siguiente formato:

[ Estado ] [ Símbolo ] → [ Nuevo Estado ] [ Escritura ] [ Desplazamiento ]

Estado = {1, 2,... N } Símbolo = {0, 1} Nuevo Estado = {1, 2,... N} U Estado de parada Escritura = {0, 1} Desplazamiento = {Izquierda, Derecha} (L, R)

Dependiendo del estado actual y el símbolo que haya en la celda actual, la máquina pasa a un estado diferente, escribe un nuevo símbolo y desplaza la cabeza de lectura/escritura a izquierda o derecha.

Cuàdruple

En cuanto a la variante cuádruple, el formato de la función de transición es el siguiente: [ Estado ] [ Símbolo ] → [ Nuevo Estado ] [ Escritura Desplazamiento ]

Estado = {1, 2,... N } Símbolo = {0, 1} Nuevo Estado = {1, 2,... N} U Estado de parada Escritura = {0, 1} Desplazamiento = {Izquierda, Derecha} (L, R)

Es decir, la máquina o escribe un nuevo símbolo en la cinta o desplaza la cabeza de lectura / escritura, pero nunca las dos cosas a la vez.

Este tipo de máquinas tienen algunas restricciones más:

I. Cuando la máquina para solo puede haber una secuencia de 1´s en la cinta.

II. La máquina debe parar con la cabeza de lectura / escritura sobre el 1 situado más a la izquierda de la secuencia.

III. La máquina debería parar después de leer un 1.

La productividad en estas máquinas se define como la longitud de la secuencia de 1´s producida por la máquina de Turing cuando comienza en una cinta en blanco y para al leer el 1 más a la izquierda de la secuencia, dejando el resto de la cinta en blanco. Las máquinas que no paran o que paran en otra situación tienen productividad 0. Cómo apunte cabe destacar que estas máquinas son menos productivas que las quíntuples.

Parada Explícita.

La máquina lee, realiza una acción y a continuación se produce la parada.

Parada implícita.

La máquina lee, y directamente realiza la parada.

.

presentadores:

Pérez Martínez Erika, Francisco Navarro Teresa de Jesús, Montiel Santos Imelda y Mar Gaspar José Eduardo

Referencias:

http://campusvirtual.unex.es/cala/epistemowikia/index.php?title=Castor_Afanoso/Maquinas_Turing

Este link contiene los tipos de variantes de una máquina de Turing pero es un software para interactuar y practicar los autómatas y realizar las transiciones.

http://pisuerga.inf.ubu.es/cgosorio/THOTH/variantes.htm

http://delta.cs.cinvestav.mx/~gmorales/complex/node22.html

http:\\www.laspaginasdelsaber.com\teoriadelacomputationaly\masmamadasmiaslol.htm

http://www.slideshare.net/cchicaiza/mquina-de-turing