funciones computables reducibilidad de turing

funciones computables

las funciones computables   son una formulacion de la intuitiva de algoritmo segun Church -Turing son exatamente las funciones que puede ser calculadas con una maquina de calculo.

las funciones computables son usadas para discutir computabilidad sin referise a ningun modelo de computacion concreto, como maquina de Turing o maquina de registro. los axiomas de Blum puede ser usados para definir una teoria de complejidad computacional abstracta sobre sobre el congunto de funciones computables.

en la teoria complejidad computacional, el problema de determinar la complegidad de uana funcion computable esta conocido como un problema de funciones.

Una funcion parcial se llama computable si el grafico de f es un conjunto recursivamente enumerable. el comjunto de funciones parciales computables con un parametro es normalmente escrito

Definición

Una función parcial

se llama parcialmente computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito o si el número de parámetros puede deducirse del contexto.
Una función total

se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe o .
Una función computable f se llama predicado computable si es una función con valor booleano, es decir

A veces, por razones de claridad, se escribe una función computable como

Podemos fácilmente codificar g en una nueva función

usando una función de parciales.

Reducibilidad de Turing

la  nicion mas fundamental de la reducibilidad es un sistema A de número naturales está Turing reducible a un sistema B si y solamente si hay máquina de Turing del oráculo eso, cuando está funcionado con B pues su sistema del oráculo, computará función del indicador (función característica) de A. Equivalente, A es Turing reducible a B si y solamente si hay un algoritmo para computar la función del indicador para A a condición de que es el algoritmo se proporciona los medios de contestar correctamente a las cuestiones de la forma “ n en B?".

La reducibilidad de Turing sirve como línea que se divide para otras nociones de la reducibilidad porque, según Tesis de la Iglesia-Turing, es la relación más general de la reducibilidad que es eficaz. Las relaciones de la reducibilidad que implican la reducibilidad de Turing han venido ser conocidas como reducibilities fuertes, mientras que son los que son implicadas por la reducibilidad de Turing reducibilities débiles. Equivalente, una relación fuerte de la reducibilidad es una que grados forman una relación de equivalencia más fina que los grados de Turing, mientras que una relación débil de la reducibilidad es una que grados forman una relación de equivalencia más gruesa que la equivalencia de Turing.

Reducciones más fuertes que la reducibilidad de Turing

Los reducibilities fuertes incluyen

• Reducibilidad de One-one: A es el one-one reducible a B si hay una función computable del one-one f con A(x) = B(f(x)) para todos x.
• Mucho-uno reducibilidad: A está mucho-uno reducible a B si hay una función computable f con A(x) = B(f(x)) para todos x.
• Verdad-tabla reducible: A es la verdad-tabla reducible a B si A es Turing reducible a B vía una sola (oráculo) máquina de Turing que produce una función total concerniente a cada oráculo.
• Verdad-tabla débil reducible: A es la verdad-tabla débil reducible a B si hay una reducción de Turing de B a A y una función recurrente f cuál limita uso. Siempre que A es la verdad-tabla reducible a B, A está también la verdad-tabla débil reducible a B, puesto que uno puede construir un límite recurrente en el uso considerando el uso máximo en cualquier oráculo, que sea computable si la reducción es total en todos los oráculos.
• Reducible positivo: A está reducible positivo a B si y solamente si A es la verdad-tabla reducible a B de una manera que una puede computar para cada x átomos que consisten en de un fórmula de la forma B(0), B(1), ... tales que estos átomos están combinados cerca y y o, donde y de a y b es 1 si a = 1 y b = 1 y así sucesivamente.
• Reducible disyuntivo: Similar a reducible positivo con el constreñimiento adicional que solamente o se permiten.
• Reducibilidad conjuntiva: Similar a la reducibilidad positiva con el constreñimiento adicional que solamente y se permiten.
• Reducibilidad linear: Similar a la reducibilidad positiva pero con el constreñimiento ese todos los átomos de la forma B(n) son combinados por exclusiva o. Es decir A está reducible linear a B si y solamente si cálculos de una función computable para cada uno x un sistema finito F(x) dado como lista explícita de números tales que x ∈ A si y solamente si F(x) contiene un número impar de elementos de B.

Construcción modular de una máquina

Objetivo de creación modular de una maquina de Turing

Mediante esta técnica se puedan desarrollarse maquinas de Turing complejas a partir de  bloques de elementales a partir de maquinas mas pequeñas  mediaste diagramas de transiciones.

La construcción de maquinas de Turing se lleva a cabo 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.

Pasos para la construcción de una máquina de Turing

1.-Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.
2.-Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que nos 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 y.

Ejemplificación de  dicha construcción.
 

Los diagramas compuestos para la construcción modular de una maquina de Turing

Son aquellos en los que cada uno de los bloques de construcción se representa como un nodo, con flechas entre dichos nodos para indicar las transiciones entre bloques.

Se puede combinar dos máquinas de Turing permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece.  El contenido de la cinta cuando comienza la ejecución de la segunda máquina de Turing, está formado por todo lo que dejó la primera máquina de Turing, y la cabeza de l/e de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.

Un sistema Turing completo es aquel que puede simular el comportamiento de una máquina de Turing.  Es evidente que salvando los problemas de memoria, los ordenadores modernos y  los lenguajes de programación de uso general, son sistemas de Turing completos.  También es evidente, que con independencia de su forma concreta, cualquier dispositivo que se comporte como un sistema de Turing completo, puede en principio ejecutar cualquier cálculo que realice cualquier computador.

Nota: Observe que la anterior afirmación no menciona para nada la posible dificultad de escribir el programa o del tiempo que pueda emplear en realizar el cálculo (cualquier cálculo que pueda hacer un ordenador puede teóricamente efectuarse con papel y lápiz).

           

Una máquina de Turing 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.

Maquina s de Turing Compuesta.

- Construcción de máquinas de Turing complejas a partir de bloques elementales.

- Transferencia de control entre máquinas:

- Transferencia de control con varios símbolos:

→ M1x→M2→

M1x, y, z→}w→M2w→

CONSTRUCCIÓN MODULAR DE MÁQUINAS DE TURING