Las maquinas turing

Una máquina de Turing con una 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.
* 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ímboloque se puede 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.

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 unnuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
avanzar el cabezal lector/escritor hacia la derecha.
avanzar el cabezal lector/escritor hacia la izquierda.
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ácter leídode 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 máquina de chur-turin thesis
Fue formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX, y a pesar de que existen múltiples formulaciones equivalentes, se utilizara una formulación simple y aceptada como dicha tesis, que se obtiene apartir de las revisiones conjuntas entre Alonzo Church y Alan M. Turing de sus respectivos trabajos:
Puesto que se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, es decir:
* Todo lo que es computable (entendiéndose computable como "Lo que se puede tomar en cuenta oevaluar") es Turing-computable.
Eso implica que las máquinas de Turing realmente capturan la noción de lo que es un algoritmo o un procedimiento efectivo llevado a cabo por un humano o por una máquina.
* |
Aunque originalmente la tesis que Alonzo Church formulara dice:
* Tesis de Church: "(Church-Turing) A function of positive integers is effectively calculable only if recursive."
Cuyatraducción sería:
* Una función de enteros positivos es efectivamente calculable sólo si es recursiva.
Versión de la Tesis de Church-Turing más utilizada: Todo algoritmo o procedimiento efectivo es Turing-computable.
Otra versión simplificada de la anterior es:
* Todo lo que es computable es Turing-computable.
Motor de diferencia
Motor de diferencia fue diseñado tabular funciones polinómicas, y comoambos logarítmico y funciones trigonométricas puede ser aproximado por polinomios.

* En el tiempo de Babbage las tablas numéricas eran calculadas por los seres humanos que fueron llamados las computadoras del `,' significando “uno quién computa,” mucho pues un conductor es “uno quién conduce.” En Cambridge él vio el alto índice de error de esto proceso humano-conducido y comenzó su trabajo devida de intentar calcular las tablas mecánicamente. Él comenzó en 1822 con lo que él llamó el motor de diferencia, hecho para computar valores de funciones polinómicas. Desemejante de los esfuerzos similares del tiempo, el motor de diferencia de Babbage fue creado para calcular una serie de valores automáticamente. Usando el método de diferencias finitas, era posible evitar la necesidad de lamultiplicación y de la división.
* El primer motor de diferencia fue compuesto de alrededor 25.000 porciones, pesado quince toneladas (13.600 kilogramos), y estado parados 8 pies (2.4 m) de alto. Aunque él recibió el financiamiento amplio para el proyecto, nunca fue terminado. Él diseñó más adelante una versión mejorada, “No. de motor de diferencia. 2 ", que no fue construido hasta 1989-1991,...