¿Por qué son completos los lenguajes funcionales de Turing?

Quizás mi comprensión limitada del tema es incorrecta, pero esto es lo que entiendo hasta ahora:

• La programación funcional se basa en el cálculo Lambda, formulado por Alonzo Church.

• La programación imperativa se basa en el modelo de máquina de Turing, realizado por Alan Turing, estudiante de Church.

• El cálculo Lambda es tan poderoso y capaz como la Máquina de Turing,
  lo que significa que son equivalentes en potencia computacional.

Si la programación funcional se basa en el cálculo de Lambda y no en la máquina de Turing, ¿por qué se describe que algunos (o todos) son completos de Turing, y no Lambda completa o algo así? ¿Es el término "integridad de Turing" especial de alguna manera para las máquinas de Turing, o es solo una palabra?

Por último, si los lenguajes imperativos se basan en la máquina de Turing, y las computadoras son básicamente máquinas de Turing, sin memoria infinita, ¿eso significa que funcionan mejor que los lenguajes de programación funcionales en nuestras PC modernas?

Si ese es el caso, ¿cuál sería el equivalente de una máquina de cálculo lambda?

Sé que esto parece ser 3 preguntas separadas, pero todas están estrechamente relacionadas, y cada una depende de que la pregunta anterior sea una pregunta válida para empezar.

En pocas palabras :

Lo que caracteriza a los lenguajes de programación imperativos tan cercanos a las máquinas de Turing y a las computadoras habituales, como las PC, (más cerca de las máquinas de acceso aleatorio (RAM) en lugar de las máquinas de Turing) es el concepto de una memoria explícita que se puede modificar para almacenar (resultados intermedios ) Es una vista de autómatas de cómputo, con un concepto de estado (que comprende tanto el control de estado finito como el contenido de memoria) que puede cambiar a medida que avanza el cómputo.

La mayoría de los otros modelos son más abstractos. Aunque pueden expresar el cálculo como una sucesión de pasos de transformación de una estructura original, estas transformaciones se aplican en una especie de universo intemporal de significados matemáticos. Esto puede preservar propiedades, como la transparencia referencial, que pueden simplificar el análisis matemático. Pero está más alejado de los modelos físicos naturales que dependen de la concpet de la memoria.

Por lo tanto, no hay máquinas funcionales naturales, excepto en un sentido más amplio como se explica a continuación, ya que el software no es realmente separable del hardware.

La referencia a Turing como criterio de computabilidad proviene probablemente del hecho de que su modelo, la máquina de Turing, estaba más cerca de esta restricción de realización física, lo que lo convirtió en un modelo de computación más intuitivo.

Consideraciones adicionales :

Hay muchos modelos de computación, que fueron diseñados para capturar de la manera más general posible el concepto de computación. Incluyen máquinas de Turing, en realidad en muchos sabores diferentes, el cálculo lambda (sabores también), sistemas de reescritura semi-Thue, función recursiva parcial, lógica combinatoria.

Todos capturan algunos aspectos de las diversas técnicas utilizadas por los matemáticos para expresar o realizar cálculos. Y la mayoría se han utilizado hasta cierto punto como la base de algún diseño de lenguaje de programación (por ejemplo, Snobol para reescribir sistemas, APL para combinadores, Lisp / Scheme para cálculo lambda) y a menudo se pueden combinar de diversas maneras en lenguajes de programación modernos.

Un resultado importante es que todos estos modelos de computación demostraron ser equivalentes, lo que lleva a la tesis de Church-Turing de que ningún modelo de computación físicamente realizable puede hacer más que cualquiera de estos modelos. Se dice que un modelo de cómputo es Turing completo si se puede demostrar que es equivalente a uno de estos modelos, por lo tanto, equivalente a todos ellos.

El nombre podría haber sido diferente. La elección de la máquina de Turing (TM) como referencia probablemente se deba al hecho de que es probablemente el más simple de estos modelos, imitando de cerca (aunque de manera simplista) la forma en que un humano calcula y bastante fácil de implementar (en una forma limitada limitada) ) como dispositivo físico, hasta tal punto que las máquinas de Turing se han construido con juegos de Lego . La idea básica no requiere sofisticación matemática. Probablemente sea la simplicidad y la realización del modelo lo que le dio esta posición de referencia.

En el momento en que Alan Turing creó su dispositivo informático, otras propuestas estaban sobre la mesa para servir como definición formal de computabilidad, un tema crucial para los fundamentos de las matemáticas (ver Entscheidungsproblem ). Los expertos de la época consideraron la propuesta de Turing como el trabajo conocido más convincente sobre lo que debería ser la calculabilidad (ver Computabilidad y Recursión , RI Soare, 1996, ver sección 3.2). Las diversas propuestas demostraron ser equivalentes, pero la de Turing fue más convincente. _{[de los comentarios de Yuval Filmus]}

Cabe señalar que, desde el punto de vista del hardware, nuestras computadoras no son máquinas de Turing, sino lo que se llama Máquinas de acceso aleatorio (RAM) , que también están completas.

El lenguaje puramente imperativo (lo que sea que eso signifique) son probablemente los formalismos utilizados para los modelos más básicos, como las máquinas de Turing, o el lenguaje ensamblador (omitiendo su codificación binaria) de las computadoras. Ambos son notoriamente ilegibles y muy difíciles de escribir con programas significativos. En realidad, incluso el lenguaje ensamblador tiene algunas características de nivel superior para facilitar un poco la programación, en comparación con el uso directo de las instrucciones de la máquina. Los modelos básicos imperativos están cerrados a los mundos físicos, pero no son muy utilizables.

Esto condujo rápidamente al desarrollo de modelos de cómputo de nivel superior, que comenzaron a mezclar una variedad de técnicas computacionales, como llamadas a subprogramas y funciones, denominación de ubicación de memoria, alcance de nombres, cuantificación y variables ficticias, ya utilizadas de alguna forma en matemática y lógica, e incluso conceptos muy abstractos como la reflexión ( Lisp 1958).

La clasificación de los lenguajes de programación en paradigmas de programación como imperativo, funcional, lógico, orientado a objetos se basa en la preeminencia de algunas de estas técnicas en el diseño del lenguaje y la presencia o ausencia de algunas características informáticas que imponen algunas propiedades para los programas. o fragmentos de programas escritos en el idioma.

Algunos modelos son convenientes para máquinas físicas. Algunos otros son más convenientes para una descripción de algoritmos de alto nivel, que puede depender del tipo de algoritmo que se describirá. Algunos teóricos incluso usan especificación no determinista de algoritmos, e incluso pueden traducirse en términos de programación más convencionales. Pero no hay problema de desajuste, porque desarrollamos una sofisticada tecnología de compilación / interpretación que puede traducir cada modelo a otro según sea necesario (que también es la base de la tesis de Church-Turing).

Ahora, nunca debe mirar a su computadora como hardware en bruto. Contiene circuitos booleanos que realizan un procesamiento muy elemental. Pero gran parte de esto es impulsado por microprogramas dentro de la computadora que nunca conoce. Luego tiene el sistema operativo que hace que su máquina parezca incluso diferente de lo que hace el hardware, además de eso puede tener una máquina virtual que ejecuta código de bytes y luego un lenguaje de alto nivel como Pyva y Jathon o Haskell o OCaml, que se puede compilar en código de bytes.

En cada nivel, ve un modelo de cálculo diferente. Es muy difícil separar el nivel de hardware del nivel de software para asignar un modelo computacional específico a una máquina. Y como todos son intertraducibles, la idea de un modelo de cómputo de hardware definitivo es prácticamente una ilusión.

La máquina de cálculo lambda sí existe: es una computadora que puede reducir las expresiones de cálculo lambda. Anuncio que se hace fácilmente.

Sobre arquitecturas de máquinas especializadas

En realidad, complementando la respuesta de Peter Taylor y siguiendo el entrelazamiento de hardware / software, se han producido máquinas especializadas para adaptarse mejor a un paradigma específico, y se les ha escrito su software básico en un lenguaje de programación basado en ese paradigma.

Éstas incluyen

• El Burroughs B5000 y sus sucesores (1960), adaptados para una implementación eficiente de la recursividad, representados en ese momento por el lenguaje Algol 60 .

• El Western Digital WD / 9000 Pascal MicroEngine , una máquina basada en un bytecode microprogramado especializado para el lenguaje de programación Pascal , a principios de los años ochenta.

• Varias marcas de máquinas Lisp en la década de 1980.

Fundamentalmente, estas también son estructuras de hardware imprescindibles, pero mitigadas con funciones especiales de hardware o intérpretes microprogramados para adaptarse mejor al paradigma deseado.

En realidad, el hardware especializado para paradigmas específicos no parece haber tenido éxito a largo plazo. La razón es que la tecnología de compilación para implementar cualquier paradigma en el hardware de vainilla se hizo cada vez más efectiva, por lo que el hardware especializado no era tan necesario. Además, el rendimiento del hardware mejoró rápidamente, pero el costo de la mejora (incluida la evolución del software básico) se amortizó más fácilmente en el hardware básico que en el hardware especializado. El hardware especializado no podría competir a largo plazo.

Sin embargo, y aunque no tengo datos precisos sobre esto, sospecharía que estas empresas dejaron algunas ideas que influyeron en la evolución de la arquitectura de máquinas, memorias y conjuntos de instrucciones.

Turing-complete es solo un nombre. Puedes llamarlo Abdul-complete si quieres. Los nombres se deciden históricamente y a menudo llevan el nombre de las personas "equivocadas". Es un proceso sociológico que no tiene criterios claros. El nombre no tiene significado más allá de su semántica oficial.

Los lenguajes imperativos no se basan en máquinas de Turing. Se basan en máquinas RAM. Su computadora es una máquina RAM. Las máquinas de Turing son un buen modelo teórico, pero no son un muy buen modelo de computadoras reales.

Los lenguajes de programación basados ​​en otros paradigmas pueden tener mucho éxito, aunque la CPU subyacente no los admita de forma nativa; por ejemplo, las impresoras ejecutan un lenguaje de pila. Hay más en la programación que el código de máquina.

Debido a que "Turing-complete" solo significa "puede calcular lo que una máquina de Turing puede calcular".

Parece que una de sus preguntas aún no ha sido respondida:

Si ese es el caso, ¿cuál sería el equivalente de una máquina de cálculo lambda?

Una máquina Lisp . Hardware diseñado específicamente para adaptarse al modelo de computación LISP. El artículo de Wikipedia habla sobre productos comerciales, pero mi director de estudios en la universidad tenía uno hecho a mano en su oficina.

Se demostró que los lenguajes funcionales en forma de cálculo lambda inventados por la Iglesia eran completos. Esta es una prueba matemática real que se puede encontrar en artículos científicos publicados al "reducir" el cálculo lambda a operaciones / cálculos en máquinas Turing. En la época del documento de Turings de 1936 y posteriores, se propusieron / distribuyeron diferentes modelos de cómputo "integrales". se no se dio cuenta de inmediato que todos eran equivalentes. Las pruebas de que eran equivalentes se publicaron aproximadamente a fines de la década de 1930 y 1940 después del documento de Turings.

la máquina de Turing es conceptualmente (pero no funcionalmente) más simple que los otros modelos y esa es probablemente una parte importante de la razón por la cual la integridad de Turing lleva su nombre. Otras ideas, como el cálculo lambda, son más abstractas y comenzaron / se originaron principalmente en la teoría matemática / lógica. Turing propuso una máquina teórica . una "máquina" es literalmente un "dispositivo físico". Es un objeto / construcción conceptual notable que une / unifica dos mundos diferentes, el aplicado y el teórico. le da un nuevo significado abstracto a las entidades físicas, por ejemplo, "tiempo y espacio". No es una mera coincidencia que los matemáticos a veces se refieran a "tecnología", "maquinaria" o "dispositivos" de pruebas. Turing logró fusionar ingeniosamente todo esto en su invención conceptual. su definición es bastante simple, pero su análisis exhibe algunos de los comportamientos emergentes más extraordinarios jamás vistos en la historia del pensamiento científico / matemático. Turing fue el primer científico / matemático en captar gran parte de este significado / poder / potencial.