Maquinas de Turing

TECNOLOGIA UNIVERSIDAD

INTRODUCCIÓN

Las Máquinas de Turing, se corresponden con las gramáticas sin restricciones. La peculiaridad de este tipo de gramáticas es que puedes describir cualquier suceso computable. Un suceso computable es aquél que mediante un procedimiento es capaz de transformar unas determinadas entradas en las salidas requeridas. Ésta es precisamente la capacidad que se necesita en un computador; el poder describir un procedimiento (programa) que, a partir de unas entradas, sea capaz de producir una salida. Así pues, existe una asociacion entre las Máquinas de Turing y los fenómenos computables, de forma que se dice que un proceso es computable si existe una Máquina Turing capaz de describirlo.

Una Máquina de Turing se define por la siguiente tupla:

                                                                              MT = (Г,∑,b,Q,q0,f,F)

 

(Puede quitar la publicidad ampliando la cuenta)