La teoría de la computación o funciones Turing-computables

NOMBRE DE LA MATERIA:

TEORIA DE LA COMPUTACION

NOMBRE DEL TEMA:

UNIDAD 6

GRADO: 4TO “B”

TURNO: VESPERTINO

REDUCIBILIDAD

En teoría de la computabilidad funciones computables o funciones Turing-computables son los objetos básicos de estudio. Hacen nuestras nociones intuitivas de algoritmo presicas y según el tesis Church-Turing son exactamente las funciones que pueden ser calculados con una máquina de calculación. La noción de la computabilidad de una función puede ser relativizado a un conjunto arbitrario de números naturales A, o equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas por un oracle por A o f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable matemáticos solían usar el término informal efectivamente computable.

Funciones computables son usados para discutir computabilidad sin referir a ningún modelo de computación concreto, como máquina de Turing o máquina de registros. Los axiomas de Blum puede ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables.

Según el tesis Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidos por funciones recursivos, calculo de lamda, o algoritmos de Markov.

Alternativamente se pueden definir como los algoritmos que pueden ser calculados por máquina de Turing, sístema de Post, o máquina de registros. En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable esta conocido como un problema de funciones.

Una función parcial

está llamado 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 isi el número de parámetros es claro del contexto.

Una función total

está llamado computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro es normalmente escrito o . Una función computable f está llamado predicado computable si es una función con valor booleano, o sea

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

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

usando ana función de pares.

Propiedades

• El conjunto de funciones computables contable.

• Dados dos funciones computables f yg entonces f+g, fg y fog son funciones computables.

• Funciones computables son definibles aritmeticamente.

• Una función con valor booleano f es un predicado computable si y solo si el lenguaje es recursivo.

PROBLEMAS INSOLUBLES TEORIA DE LENGUAJES

PROBLEMAS INSOLUBLES

Sea el problema Palguna el siguiente problema:

Pacept: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se detiene sobre alguna cadena?

Para demostrar que P alguna no es soluble, comenzaremos suponiendo que lo es, llegando de esta manera a un absurdo. Este absurdo tendrá lugar debido a que la solubilidad de Palguna implica la solubilidad de Pdet. Expresado de otra manera, demostramos que Pdet se reduce a Palguna. Demostración:

Supongamos que Palguna es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquina universal de Turing), Alguna, que resuelve Palguna. Alguna toma como datos de entrada la descripción de una máquina de Turing T y determina en un tiempo finito si T se detiene sobre alguna cadena o no. Es decir Alguna recibe como entrada (T) y retorna un 1 si T se detiene para alguna cadena, mientras que devuelve la salida 0 si T no se detiene para ninguna cadena. Construyamos a partir de Alguna, un procedimiento efectivo (o máquina universal de Turing)

Detención

La máquina Detención recibe como entrada un par (T’,α), el problema Palguna solo tiene como entrada una máquina de Turing, por lo que necesitamos un proceso adicional que combine T’ y α de manera que las respuestas de Alguna, respondan el problema de la detención. Este proceso adicional se lleva a cabo en la máquina universal ΔX que realiza lo siguiente:

a. Recibe como dato de entrada la máquina de Turing T’ y la cadena α.

b. Construye una máquina de Turing T tal que:

i. Para la cadena α se comporta como la máquina de Turing T’.

j. Para toda cadena que no sea α la nueva máquina T nunca se detiene o cicla indefinidamente.

Combinando la máquinas universales Alguna y ΔX, tenemos la máquina universal Detención que tiene el siguiente comportamiento:

1. Detención recibe como entrada el par (T’, α).

2. La máquina universal Detención utiliza ΔX, la cual a partir de T’ y α construye la nueva máquina de Turing T.

3. La máquina de Turing T obtenida en el paso anterior es ingresada a la máquina universal Alguna.

4. Si la respuesta de Alguna es 1 entonces T se detiene para alguna cadena. De la manera en la que construimos T esa cadena necesariamente es la cadena α (ya que para el resto sabemos que la máquina siempre cicla) como el comportamiento de T frente a la cadena α es el mismo que tiene la máquina T’ entonces podemos afirmar que T’ se detiene sobre α y que por lo tanto Detención emite un 15. Si la respuesta de Alguna es 0 entonces T no se detiene para ninguna cadena. De la manera en la que construimos T la única cadena sobre la que T podía detenerse era α y que el comportamiento frente a esta cadena era el mismo que el de la máquina T’. Podemos entonces afirmar, que la máquina de Turing T’ tampoco se detiene frente a la cadena y que por lo tanto la

...