Como advertencia, me encantaría escuchar una respuesta de alguien que participe activamente en la investigación de computabilidad. Diré desde el principio que no soy una persona así.
Alonzo Church y Alan Turing crearon dos formalismos separados casi exactamente al mismo tiempo (justo a fines de la década de 1930) que corresponden exactamente al mismo nivel de complejidad computacional: el cálculo de Lambda y la máquina de Turing, respectivamente.
Si bien el cálculo Lambda es el primer lenguaje de programación completo de Turing, las máquinas de Turing corresponden a una máquina ideal (con memoria infinita y sin partes mecánicas rompibles) a las que las máquinas de cinta en uso durante más de cuarenta años se acercaron a medida que se hacían más confiables. Dada más memoria, y así sucesivamente.
- ¿Qué tan bueno en matemáticas necesitas ser para estudiar química a nivel de pregrado?
- ¿Cómo es estudiar la postgrado en gestión de proyectos en Nueva Zelanda con respecto a las perspectivas de empleo?
- ¿Recomendarías estudiar en TU Delft?
- Cómo puntuar 100 en inglés CBSE board class 12
- ¿Por qué las universidades quieren que los estudiantes estudien en el extranjero?
Las máquinas Lambda calc y Turing proporcionan dos vistas intuitivamente diferentes al mismo objeto esencial: Lambda calc calcula el cálculo en términos de una serie de reducciones de términos que comparan el cálculo con el proceso de hacer matemáticas (o analizar lexemas en tokens sintácticos en lenguajes recursivamente enumerables, como un lingüista podría ver el cálculo).
Por el contrario, las máquinas de Turing tratan el cálculo en términos de cambios de estado y autómatas. Esto simplifica ciertos tipos de discusiones de computabilidad (los castores ocupados, o incluso los experimentos de pensamiento en estadística e investigación de IA como los aprendices de AIXI, son más fáciles de especificar en términos de máquinas de Turing, por ejemplo). La semántica operacional de los lenguajes de programación generalmente está enmarcada o especificada en términos de cambios de estado, es decir, los lenguajes de programación son lenguajes ensambladores para máquinas de Turing abstractas idealizadas. Separar las ideas de la cinta (datos de lectura-escritura) y la tabla de símbolos (finita, memoria de solo lectura) también corresponde a cómo se construyen las computadoras hoy en día: el modelo de Von Neumann, y especialmente la máquina de registro, son ejemplos de máquinas de Turing que son bastante cerca de cómo funcionan las CPU modernas.
