Teoria de la computacion

INDICE

UNIDAD IV
MAQUINA DE TURING…………………………………….…………………...………4

4.1 DEFINICION FORMAL DE UNA MAQUINA DE TURING………….……………………………………………………………....……………….4

4.2 CONSTRUCCION MODULAR DE UNA MAQUINA DE TURING…………………………………………………………………………………………..9

4.3 LENGUAJES ACEPTADOS POR LA MAQUINA DE TURIN.....………………………………………………………………………………………..14

4.4 VARIANTES DE UNA MAQUINA DETURING…………………………................................................................................................16

4.5 PROBLEMAS DE HILBERT………..……………………….………………….17

UNIDAD V
DECIBILIDAD………………………………………………………………………….18

5.1 LENGUAJES DECIBILIDAD……………………………………...……………18

5.2 EL PROBLEMA DE HALTING……………………………………….………..20

5.3 DECIBILIDAD DE TEORIAS LOGICAS……………………………………..23

UNIDAD VIREDUCIBILIDAD………………………………………………………………………24

6.1 PROBLEMAS INSOLUBLES PARA LA TEORIA DE LENGUAJE………………………..………………………………………………...25

6.2 UN PROBLEMA SIMPLE INSOLUBLE……………………………………...26

6.3 FUNCIONES COMPUTABLES………………………………………………...27

6.4 REDUCIBILIDAD DE TURING………………………………………………..27

BIBLIOGRAFIA………………………………………………………………………………...28UNIDAD IV: Maquina de Turing

La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que puedaaplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo.

Definición formal de una Maquina de Turing

Una máquina de Turing conuna sola cinta puede ser definida como una 7-tupla , donde:[]
* es un conjunto finito de estados.
* es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
* es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta.
* es el estado inicial.
* es un símbolo denominado blanco, y es el único símbolo que sepuede repetir un número infinito de veces.
* es el conjunto de estados finales de aceptación.
* es una función parcial denominada función de transición, donde es un movimiento a la izquierda y es el movimiento a la derecha.
Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolocomo símbolo de "no movimiento" en un paso de cómputo o el símbolo para indicar el alfabeto de entrada.
Funcionamiento:La máquina de Turing 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 (fig.1). Las operaciones que se pueden realizar en esta máquina se limitan a:
* avanzar el cabezallector/escritor hacia la derecha.
* avanzar el cabezal lector/escritor hacia la izquierda.

Fig.1. Visualización de una Maquina de Turing, en la que se ve el cabezal y la cinta que se lee

El cómputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) (nuevo estado, nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácterleído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
La memoria será la cinta la cual 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”. Las instrucciones que determinan el funcionamiento de la...