UNIDAD TEMATICA 3: modelos formales de computacion: automatas y maquinas

AQUI LES DEJO UNA EXPLICACION FACIL DE QUE ES UNA MAQUINA DE TURING

MÁQUINAS DE TURING

Definimos una máquina de Turing como una 7-tupla M = (K, Σ, δ, s,U), donde

K es un conjunto finito de estados

 Σ es un alfabeto de entrada

  s   es el estado inicial

 U  es el símbolo blanco o espacio vacio

  {→, ←, −} punteros (derecha, izquierda, detenerse)
"alto","si""no" ∈ K es el conjunto de estados finales o de aceptación

 δ: K x Σ → (K U {"alto","si""no"}) xΣx {→, ←, −} es una función parcial que se llama función de transición.

La máquina de Turing posee una cinta dividida en celdas, cada celda es capaz de almacenar un símbolo. Además posee una cabeza lectora/escritora que lee y escribe un símbolo en la cinta. Inicialmente la cinta contiene un simbolo de inicio en todas sus celdas. La función de transición δ transforma pares (q, s), la maquina le el simbolo que esta en la casilla que la maquina lee en ese momento y ejecuta la funcion de trancicion y desppues mueve segun el puntero y cuando la maquina llega a un estado terminal se determinala salida de la cinta

 

bibliografia: curso de algoritmos profesora Blanca Idalea de fime