¿Por qué algunos lenguajes de programación de Turing son completos pero carecen de algunas habilidades de otros lenguajes?

42

Me encontré con un problema extraño al escribir un intérprete que (debería) engancharse a programas / funciones externas: las funciones en 'C' y 'C ++' no pueden conectar funciones variadas , por ejemplo, no puedo hacer una función que llame a 'printf' con exactamente los mismos argumentos que obtuvo, y en su lugar tiene que llamar a una versión alternativa que tome un objeto variadic. Esto es muy problemático ya que quiero poder hacer un objeto que contenga un gancho anónimo.

Entonces, pensé que esto era extraño ya que Forth , JavaScript , y quizás una gran cantidad de otros idiomas pueden hacer esto muy fácilmente sin tener que recurrir al lenguaje ensamblador / código de máquina. Dado que otros lenguajes pueden hacer esto tan fácilmente, ¿eso significa que la clase de problemas que cada lenguaje de programación puede resolver en realidad varía según el idioma, a pesar de que estos lenguajes están completos ?

Mr. Minty Fresh
fuente
33
Deberías investigar las lonas de Turing . Son un tipo fascinante de lenguaje de programación que intencionalmente tiene la menor cantidad de operaciones disponibles posible mientras se está completando. La mayoría de ellos carece de tipos de datos básicos, funciones, incluso cosas simples como declarar variables. Personalmente, creo que codificarlos es muy divertido, ya que te obliga a salir de tu zona de confort para intentar algo innecesariamente difícil.
DJMcMayhem
8
Mire lo que hace una máquina de Turing, y verá que "Turing-complete" es un obstáculo muy bajo para despejar. Básicamente, todo lo que puede 'leer', 'escribir' y 'saltar' mientras admite aritmética básica es Turing-complete. Eso está muy por debajo del nivel de las características del lenguaje que estás viendo.
Aroth
2
Para ser aún más ridículo: la instrucción MOV en un procesador x86 es completa de Turing. Ver cl.cam.ac.uk/~sd601/papers/mov.pdf para más detalles.
Gareth McCaughan
3
Incluso el juego de cartas Magic: The Gathering está completo. La integridad de Turing no tiene casi nada que ver con las características de un idioma.
Mástil
2
Por cierto, también hay lenguajes de programación muy complicados que no están completos, como los correctores de pruebas.
盛安安

Respuestas:

68

Turing idiomas completos pueden calcular el mismo conjunto de funciones , que es el conjunto de funciones parciales recursivas generales. Eso es.NkN

Esto no dice nada sobre las características del lenguaje. Una máquina de Turing tiene características de composición muy limitadas. El cálculo tipo es mucho más compositivo, pero carece de muchas características que se encuentran comúnmente en los idiomas modernos.λ

La integridad de Turing no dice nada acerca de tener tipos, matrices integradas / enteros / diccionarios, capacidades de entrada / salida, acceso a la red, subprocesamiento múltiple, asignación dinámica, ...

Solo porque Java no tiene la característica X (por ejemplo, macros, tipos de rango superior o tipos dependientes), no deja de ser Turing completo de repente.

La integridad de Turing y la expresividad del lenguaje son dos nociones diferentes.

chi
fuente
42
Edwin Brady, el diseñador de Idris, (solo la mitad) usa en broma (no sé si lo inventó) el término "Tetris-complete" para expresar esta diferencia entre "puede calcular cualquier función computable en números naturales" y "puede ser usado para escribir programas no triviales que interactúan con el entorno ".
Jörg W Mittag
12
También puede mencionar que podría tener esas cosas en C / C ++. Simplemente tendría que escribir algún código que actúe como un compilador en C / C ++ para otro lenguaje que los tenga donde su código compila una cadena en su código C / C ++. Entonces puedes programar en algo como Java dentro de tu archivo C. Todo esto sería mucho trabajo, pero es posible (probablemente porque C / C ++ es Turing completo).
Shufflepants
44
@Shufflepants Sin embargo, me pregunto si es realmente útil decir "Puedo hacerlo en C ++ ya que puedo interpretar otro idioma". Por ese token, Java, ML, C ++ son equivalentes. TM con un oráculo para syscalls (I / O) también son equivalentes. Me temo que, por ese razonamiento, prácticamente todos los idiomas son igualmente expresivos. Si es así, no es una noción útil para comparar idiomas.
chi
99
@chi Tienes razón, son equivalentes. Eso es lo que significa estar Turing completo. Todo lo que se puede hacer con un sistema Turing Complete se puede hacer en otro sistema Turing Complete. Puede que no sea conveniente hacerlo en un sistema en particular. Y la conveniencia de hacer varias cosas es la forma principal en que comparamos diferentes lenguajes de programación. Pero eso no es lo que la pregunta estaba haciendo.
Shufflepants
55
@Rhymoid Si C no es Turing Complete por razones de acceso a la memoria, o porque poder enviar señales arbitrarias a un dispositivo conectado que tiene un almacenamiento arbitrariamente grande no cuenta, entonces uno podría argumentar que ningún lenguaje o dispositivo del mundo real es Turing Complete . Pero no creo que sea una línea de razonamiento muy productiva.
Shufflepants
47

La integridad de Turing es un concepto abstracto de computabilidad. Si un idioma es completo de Turing, entonces es capaz de hacer cualquier cálculo que cualquier otro lenguaje completo de Turing puede hacer.

Sin embargo, esto no dice qué tan conveniente es hacerlo. Algunas características que son fáciles en algunos idiomas pueden ser muy difíciles en otros, debido a las opciones de diseño. Turing completo sólo dice que usted puede hacer el cálculo. Como ejemplo extremo, puede ser difícil enganchar funciones varadic en C ++, pero es posible escribir un intérprete de JavaScript en C ++ que pueda enganchar funciones variadas.

El diseño del lenguaje es un arte bastante interesante. Uno de los pasos principales que uno tiene que seguir es identificar qué comportamientos desea formar la columna vertebral de su lenguaje. Estas conductas son cosas que son fáciles de hacer en su idioma porque están integradas en la planta baja. Tomamos decisiones de diseño sobre qué características incluir en cada idioma.

En cuanto a su ejemplo particular, cuando se desarrolló C, fue diseñado para funcionar muy cerca de la forma en que funcionaban los lenguajes ensambladores de la época. Las funciones variadas simplemente empujaron argumentos a la pila, con muy poca seguridad de tipografía. La implementación de estas funciones variadas se dejó al compilador, para garantizar la máxima portabilidad. En consecuencia, se hicieron muy pocas suposiciones sobre las capacidades del hardware. Para cuando llegó JavaScript, la escena había cambiado. Ya opera en una máquina virtual como lenguaje interpretado, por lo que el equilibrio cambia hacia la conveniencia. Permitir el enganche de funciones variadas se vuelve razonable. Incluso en el caso de JavaScript compilado Just In Time, nuestros compiladores están dispuestos a almacenar mucha más información adicional sobre los argumentos que los compiladores C de antaño estaban dispuestos a almacenar.

Cort Ammon
fuente
1
@Wildcard Consideraría (prácticamente) todos los compiladores como incorrectos. La mayoría de los idiomas son completos de Turing, pero eventualmente necesitan ser interpretados por / compilados en ensamblador, lo cual no es así. Pero esta es una limitación física necesaria: el hardware nunca es poderoso. Aún así, la computabilidad ofrece muchos conceptos útiles que "se aplican", en un sentido práctico, a las computadoras del mundo real.
chi
3
@Wildcard En ese sentido trivial. El ensamblaje (y C) tiene punteros de tamaño fijo, que pueden abordar solo una cantidad limitada de memoria. Podríamos, teóricamente hablando, definir un ensamblaje donde los punteros son naturales ilimitados, pero ya no lo llamaría "ensamblaje", lo llamaría URM o algo así. En la práctica, simplemente pretendemos que los límites físicos son lo suficientemente grandes como para permitir que nuestros programas se ejecuten, por lo que incluso si una computadora es solo una máquina de estados finitos (lo que implica que no puede, por ejemplo, realizar la suma), pensamos más en ello como una máquina de Turing ( entonces la adición es factible).
chi
44
@chi Eso no es del todo exacto. En primer lugar, prácticamente todos consideran que C es Turing completo porque generalmente asignamos esa frase en torno al supuesto de que "tiene suficiente memoria". Para el número muy pequeño de personas que tienen que preocuparse por la redacción más estricta donde tales suposiciones no son válidas, C no especifica el tamaño de un puntero y no especifica un límite en la cantidad de memoria que se puede abordar. Entonces, incluso en el sentido más estricto de "Turing completo", C es de hecho Turing completo.
Cort Ammon
3
@CortAmmon Tengo que estar en desacuerdo. Si formalizamos la semántica de C, tratando de incorporar la suposición de "suficiente memoria", fracasaríamos ya que sizeof(void *)el estándar ISO C nos obliga a evaluar algo. Esto nos obliga a limitar la cantidad de memoria para cualquier programa dado, a algo grande, pero aún así un límite. Por ejemplo, no puedo escribir un programa cuya semántica esté agregando dos naturales arbitrarios. C aún podría hacerse Turing poderoso a través de E / S, utilizando archivos como cintas TM (como señala @Hurkyl arriba). Estoy de acuerdo en que esto no es un problema en la práctica.
chi
77
Sugiero el nuevo lenguaje C-inf, que es exactamente como C, excepto cuando se asigna demasiada memoria a través de recursión o asignación de montón, el programa se aborta, se recompila con un valor mayor para sizeof (void *) y sizeof (size_t), y comienza a correr nuevamente desde el principio.
gnasher729
26

Piense en los lenguajes de programación como diferentes vehículos terrestres: bicicletas, automóviles, aerodeslizadores, trenes.

Turing Completeness dice que "este vehículo puede ir a cualquier lugar al que pueda ir cualquier otro vehículo". Es decir, puede calcular todas las mismas funciones. Entrada a salida, de principio a fin.

Pero, esa declaración no dice nada acerca de cómo llegar allí. Podría estar en rieles, podría estar en carreteras, podría estar en el aire. Del mismo modo, Turing Completeness no dice nada acerca de cómo se calcula una función. Puede usar recursividad, iteración o algunos autómatas celulares extraños. Puede usar tipos o no, puede usar técnicas dinámicas o estáticas. Pero, si todo lo que considera son funciones (o conjuntos / lenguajes formales) que puede calcular, siempre que Turing Complete, estas características le otorgan el mismo poder.

jmite
fuente
44
Esta es una gran analogía. También se extiende muy bien a la pregunta que he visto en otras partes de este sitio, sobre si podría haber otros modelos de cómputo que superen a una máquina de Turing: en esta analogía, los aviones y naves espaciales son más que Turing Complete, y las lanchas rápidas son otro tipo de máquina por completo. :)
Comodín
2
Un viaje más rápido que la luz es probablemente una mejor analogía para la computación super-Turing. Se puede ser posible, pero la mayoría de la gente piensa que no es.
jmite
@jmite Por supuesto, todavía no hay evidencia que sugiera que nuestros cerebros sean computadoras súper resistentes. Nuestra incapacidad (aparente) de considerar máquinas que no son de turing podría derivarse de eso, aunque no es necesariamente una barrera insuperable. Los aviones son en realidad una analogía bastante buena: simplemente van "rectos" entre dos puntos, ignorando el terreno. Si pudiéramos ignorar la topología del espacio-tiempo mismo, también podríamos volar más rápido que la luz. No es que esté diciendo que es posible ignorar la topología del espacio-tiempo, recuerda :)
Luaan
1
@Luaan Correcto, pero nuestros cerebros no necesariamente necesitan ser super-Turing para comprender una computadora súper-Turing. Puedo describir la semántica de una máquina de Turing usando un lenguaje de terminación más débil, como el cálculo de Lambda simplemente tipeado, escribiendo una función que tome una TM y su estado, y la lleve al siguiente estado. Realmente no puedo ejecutar la máquina en ese idioma (porque podría tomar infinitos pasos), pero puedo escribir cómo se ve cada paso.
jmite
@Luaan, "todavía no hay buena evidencia que sugiera que nuestros cerebros son computadoras super-turing" , tal vez, pero tampoco hay evidencia que sugiera que la mente humana es solo una máquina de Turing. Dado que no hay una máquina de Turing que pueda apuntar a ningún lugar que no pueda rastrearse a ideas originadas por una mente humana, todavía existe la distinción de que la vida puede originar ideas, y los artilugios mecánicos no. Pero en cuanto a los modelos de computación, creo que las máquinas de Turing abarcan con éxito todo lo que razonablemente podría llamarse "computación", ideas y sueños y demás.
Comodín el
17

Lo que esencialmente está preguntando es la diferencia entre el poder computacional y lo que comúnmente se llama poder expresivo (o simplemente expresividad ) de un lenguaje (o sistema de cómputo).

Potencia de cálculo

El poder computacional se refiere a qué tipos de problemas puede calcular el lenguaje. La clase de potencia computacional más conocida es la que es equivalente a una máquina universal de Turing . Hay una gran cantidad de otros sistemas de computación, tales como acceso aleatorio Máquinas , λ-cálculo , SK cálculo combinador , funciones mu-recursivo , WHILEprogramas, y muchos otros. Y resulta que todos estos pueden simularse entre sí, lo que significa que todos tienen el mismo poder computacional.

Esto da lugar a la Tesis de Church-Turing (llamada así por Alonzo Church que creó el cálculo λ y Alan Turing que creó la Máquina Universal de Turing). La tesis de la Iglesia de Turing es una hipótesis sobre la computabilidad con dos aspectos:

  1. todos los sistemas de computación capaces de computación general son igualmente poderosos y
  2. un ser humano que sigue un algoritmo puede calcular exactamente las funciones que una máquina de Turing (y, por lo tanto, cualquiera de los otros sistemas) puede calcular.

Sin embargo, el segundo es más importante en el campo de la filosofía de la mente que la informática.

Sin embargo, hay dos cosas que la Tesis de Turing de la Iglesia no dice, que son muy relevantes para su pregunta:

  1. qué tan eficientes son las diversas simulaciones y
  2. cuán conveniente es la codificación de un problema.

Un ejemplo simple para (1): en una máquina de acceso aleatorio, copiar una matriz requiere un tiempo proporcional a la longitud de la matriz. Sin embargo, en una máquina de Turing, lleva un tiempo proporcional al cuadrado de la longitud de la matriz, porque la máquina de Turing no tiene acceso aleatorio a la memoria, solo puede moverse a través de la cinta una celda a la vez. Por lo tanto, necesita moverse a través de los n elementos de la matriz n veces para copiarlos. Por lo tanto, diferentes modelos de cálculo pueden tener diferentes características de rendimiento, incluso en el caso asintótico, donde tratamos de abstraernos de los detalles de implementación.

Abundan los ejemplos para (2): tanto el cálculo λ como Python son completos de Turing. ¿Pero prefieres escribir un programa en Python o en cálculo λ?

También hay una tercera arruga que he eludido hasta ahora: todos esos sistemas originales fueron diseñados por lógicos, filósofos o matemáticos, no por informáticos ... simplemente porque las computadoras y, por lo tanto, la informática no existían. Todo esto se remonta a principios de la década de 1930, incluso antes de los primeros experimentos de Konrad Zuse (que de todos modos no eran programables y / o Turing completos). Solo hablan de "funciones computables en los números naturales".

Ahora, como resultado, hay muchas cosas que puedes expresar como funciones en números naturales; después de todo, nuestras computadoras modernas incluso funcionan con mucho menos que eso (básicamente 3-4 funciones en los números 0 y 1, y eso es todo ), pero, por ejemplo, ¿qué función calcula un sistema operativo?

Esta noción de E / S, efectos secundarios, interactuando con el medio ambiente, no está captada por la idea de "funciones sobre números naturales". Y, sin embargo, es algo importante, ya que, como Simon Peyton Jones dijo una vez: "Todo lo que hace una función pura sin efectos secundarios es calentar tu CPU" , a lo que un miembro de la audiencia respondió "en realidad, eso es un lado -efecto, también! "

Edwin Brady , el diseñador de Idris , (solo la mitad) usa en broma (no sé si lo inventó) el término "Tetris-complete" para expresar esta diferencia entre "puede calcular cualquier función computable en números naturales" y "puede ser usado para escribir programas no triviales que interactúan con el entorno ". Aún más irónicamente, demuestra esto al implementar un clon de Space Invaders en Idris , pero dice que confía en que Tetris se reduce a Space Invaders.

Otra cosa a destacar es que no solo la equivalencia de Turing no es necesariamente suficiente para hablar sobre la escritura de programas "útiles", sino que puede que OTOH ni siquiera sea necesario . Por ejemplo, SQL solo se ha convertido en equivalente de Turing con ANSI SQL: 1999 , pero aún era útil antes de eso. De hecho, algunos podrían argumentar que hacer que sea equivalente a Turing no ha aumentado su utilidad en absoluto. Hay muchos lenguajes específicos de dominio que no son equivalentes a Turing. El lenguaje de descripción de datos generalmente no es (y no debería ser). Total Languages ​​obviamente no puede ser equivalente a Turing, pero aún puede escribir bucles de eventos, servidores web o sistemas operativos en ellos. También hay idiomas que son equivalentes a Turing pero que en realidad se consideran un error.

Entonces, en general, la equivalencia de Turing no es terriblemente interesante, a menos que desee analizar estáticamente los programas.

Expresividad

Suponiendo que nuestro sistema de computación es computacionalmente lo suficientemente poderoso como para resolver nuestro problema, lo que tenemos que hacer a continuación es expresar nuestro algoritmo para resolver ese problema en algún tipo de notación formal para ese sistema. En otras palabras: necesitamos escribir un programa en algún lenguaje de computadora. Ahí es donde entra en juego la noción de expresividad .

Se refiere esencialmente a lo "fácil" o "agradable" que es escribir nuestro programa en nuestro lenguaje de programación particular. Como puede ver, la noción es bastante vaga, subjetiva y más psicológica que técnica.

Sin embargo, hay intentos de definiciones más precisas. El más famoso (y el más riguroso que conozco) es de Matthias Felleisen en su artículo Sobre el poder expresivo de los lenguajes de programación (las dos primeras páginas contienen una introducción suave, el resto del documento es más carnoso).

La intuición principal es la siguiente: cuando se traduce un programa de un idioma a otro idioma, algunos de los cambios que necesita realizar están contenidos localmente (como, por ejemplo, convertir FORbucles en WHILEbucles o bucles en GOTOs condicionales ), y algunos requieren un cambio a lo global estructura del programa.

Cuando puede reemplazar una característica de un idioma con una característica diferente de un idioma diferente por solo transformaciones locales, entonces se dice que estas características no tienen efecto sobre el poder expresivo. Esto se llama azúcar sintáctico .

Por otro lado, si requiere un cambio en la estructura global del programa, se dice que el idioma al que está traduciendo no puede expresar la función. Y se dice que el lenguaje del que está traduciendo es más expresivo (con respecto a esta característica).

Tenga en cuenta que esto proporciona una definición de expresividad objetivamente medible. Tenga en cuenta también que la noción depende del contexto de la característica, y es comparativa. Entonces, si todos los programas en el idioma A se pueden traducir al idioma B con solo cambios locales, y hay al menos un programa en el idioma B que no se puede traducir a A con solo cambios locales, entonces el idioma B es estrictamente más expresivo que el idioma UNA. Sin embargo, el escenario más probable es que muchos programas en ambos idiomas se pueden traducir de un lado a otro, pero hay algunos programas en ambos idiomas que no se pueden traducir al otro. Esto significa que ninguno de los idiomas es estrictamente más expresivo que el otro, solo tienen características diferentes que permiten que diferentes programas se expresen de diferentes maneras.

Esto proporciona una definición formal de lo que significa ser "más expresivo", pero aún no capta las nociones psicológicas detrás del fenómeno. Por ejemplo, el azúcar sintáctico, de acuerdo con este modelo, no aumenta el poder expresivo de un idioma, ya que puede traducirse utilizando solo cambios locales. Sin embargo, sabemos por experiencia que tienen FOR, WHILEy IFdisponible, incluso si son de azúcar sintáctica para simplemente condicionales GOTOmarcas expresar nuestra intención más fácil .

El hecho es que diferentes idiomas tienen características diferentes que hacen que expresar diferentes formas de pensar sobre un problema sea más fácil o más difícil. Y algunas personas pueden encontrar una manera de expresar su intención más fácilmente y otras una manera diferente.

Un ejemplo que encontré en la etiqueta Ruby en StackOverflow: muchos usuarios que siguen la etiqueta Ruby afirman que los bucles son más fáciles de entender que la recursividad y la recursión es solo para programadores funcionales avanzados y los bucles son más intuitivos para los recién llegados, pero he visto múltiples casos de recién llegados que intuitivamente escriben código como este:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Lo que generalmente lleva a varias personas a comentar que "esto no funciona" y "lo están haciendo mal" y la "forma correcta" es esta:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Entonces, claramente, hay algunas personas para quienes la recursividad de la cola es una forma más natural de expresar el concepto de "bucle" que las construcciones de bucle.

Resumen

El hecho de que dos idiomas sean equivalentes a Turing dice una y exactamente una cosa: que pueden calcular el mismo conjunto de funciones en números naturales que una máquina de Turing. Eso es.

No dice nada acerca de qué tan rápido calculan esas funciones. No dice nada sobre la facilidad de expresar esas funciones. Y no dice nada acerca de qué más pueden hacer además de calcular funciones en números naturales (por ejemplo, vincular a bibliotecas C, leer la entrada del usuario, escribir la salida en la pantalla).

¿eso significa que la clase de problemas que cada lenguaje de programación puede resolver realmente varía según el idioma, a pesar de que estos lenguajes están completos?

Sí.

  1. Hay problemas que no están cubiertos por el término "Turing-complete" (que solo se refiere a las funciones informáticas en números naturales) como la impresión en la pantalla. Se pueden completar dos idiomas en Turing, pero uno puede permitir la impresión en la pantalla y el otro no.
  2. Incluso si ambos idiomas pueden resolver los mismos problemas, eso no dice nada sobre cuán compleja es la codificación y lo fácil que es expresar esta codificación. Por ejemplo, C puede resolver todos los problemas que Haskell puede, simplemente escribiendo un intérprete de Haskell en C ... ¡pero primero debe escribir el intérprete de Haskell para resolver un problema de esta manera!
Jörg W Mittag
fuente
7

Todos los lenguajes de programación completos de Turing pueden implementar el mismo conjunto de algoritmos. Entonces, si ve que algún algoritmo es muy difícil de implementar en un idioma en particular, no significa que sea imposible.

Recuerde que un lenguaje consiste en sintaxis y semántica. A veces, el conjunto de palabras que pertenecen a algún idioma no es mínimo para ser considerado Turing completo, hay características que facilitan las cosas (es por eso que se llaman características ). Si elimina esas características, el idioma aún está completo.

Algunos de estos pueden ser de interés:

Euge
fuente
5

Todos los lenguajes completos de Turing pueden calcular las mismas cosas.

Si intenta implementar un lenguaje moderno, notará que la mayoría de sus características no agregan ninguna capacidad computacional. Muchas de esas características pueden reducirse a otras más simples que ya existen en el mismo idioma.

Aquí hay unos ejemplos:

  • Si no tiene enumeraciones, puede usar enteros.
  • Si no tiene buffers que conozcan su tamaño, puede crear un tipo que contenga un tamaño y un buffer que no conozca su tamaño.
  • Si no tiene una verificación de límites de los búferes, puede verificar el índice cada vez que los use.
  • Si no tiene funciones variadas, puede crear una función que tome un búfer que conozca su tamaño y leer de ese búfer la misma información que obtendría de los argumentos formales.
  • Si no tiene operadores, puede usar funciones.
  • Si no tiene tipos que pueden heredarse entre sí, puede crear tipos que se contengan entre sí y acceder a ellos a través de un nivel adicional de indirección, con el subtipo que es simplemente una transformación del identificador de todo el tipo a un manejar al tipo contenido.
  • Si no tiene delegados pero tiene punteros de función, puede crear un tipo que contenga el objeto de referencia y un puntero de función.
  • Si no tiene delegados pero tiene interfaces, puede declarar una interfaz que contenga un único método con la firma que desee.
  • Si no tiene tipos genéricos, puede usar tipos no genéricos que solo asuman los límites superiores o inferiores que le interesan (y tal vez realice los cambios apropiados en los puntos de uso, para mantener contento al compilador).
  • Si no tiene un sistema de tipo lineal / afín, puede evitar usar cualquier variable más de una vez.
  • ...y así.

El diseño del lenguaje principal se enfoca en características que hacen que sea más fácil y conveniente para nosotros calcular las cosas más rápido, reconocer nuestros errores antes, programar contra componentes desconocidos, hacer que el paralelismo sea más seguro, etc.

Las cosas puramente computacionales se concretaron hace mucho tiempo.

Theodoros Chatzigiannakis
fuente
4

Las respuestas existentes señalan correctamente que la integridad de Turing no es una buena manera de comparar idiomas. De hecho, casi todos los idiomas están completos en Turing. ("Si todos son especiales, nadie es especial", como solía decir The Incredibles).

Sin embargo, es posible comparar la expresividad de los lenguajes con la precisión matemática. Eche un vistazo a Felleisen sobre el poder expresivo de los lenguajes de programación . Aproximadamente, la idea es hacer la siguiente pregunta: ¿Puedo convertir cualquier programa en el idioma A en un programa en el idioma B haciendo solo cambios locales ? En otras palabras, Felleisen le da una forma matemáticamente precisa a su intuición.

rgrig
fuente
2

Además de las respuestas de todos los demás, aquí hay otra analogía.

Para lavar la ropa, necesita tres cosas: un depósito que contenga agua, un detergente de algún tipo y un mecanismo de agitación. Esto podría realizarse de muchas maneras. El depósito de agua es cualquier cosa que contenga suficiente agua (por ejemplo, una bañera, un lago, un río). El mecanismo de agitación podría ser un dispositivo mecánico, una tabla de lavar o incluso una roca contra la cual se golpea la ropa. Y los detergentes también vienen en varias formas.

Entonces, ¿cuál es la diferencia entre una lavadora moderna computarizada y una roca al lado de un río?

Se reduce a tres cosas: eficiencia, seguridad y conveniencia. Algunos métodos de lavado usan menos energía, contaminan menos el medio ambiente, usan menos agua, etc. Algunos métodos de lavado requieren actividades manuales menos repetitivas (que resultan en lesiones) o estar afuera en condiciones climáticas adversas. Y algunos métodos de lavado no requieren que un humano cuide el proceso.

Los lenguajes de programación completos de Turing son de uso general, por lo que se asignan a más de una tarea. Sin embargo, para una tarea determinada, algunos lenguajes de programación son más eficientes, más convenientes y más seguros (en el sentido de que menos pueden salir mal cuando el programa se usa realmente) que otros.

Seudónimo
fuente
2

Otros han proporcionado muchas buenas respuestas, pero no mencionan explícitamente una advertencia que una vez me confundió mucho: la integridad de Turing no implica que un lenguaje pueda expresar funciones computables arbitrarias de sus entradas a sus salidas. Es más débil: debe haber alguna forma de representar el dominio y el rango del conjunto de funciones computables como entradas y salidas de modo que cada una de estas funciones se asigne a un programa que tome una representación de sus entradas a las salidas correspondientes.

Tomemos, por ejemplo, un lenguaje que expresa máquinas de Turing. Cada programa en el idioma es una máquina de Turing.

Ahora considere el sublenguaje de todas las máquinas de Turing que leen y escriben solo los caracteres a, b y en blanco. Está completa, pero no puede expresar ningún programa que, por ejemplo, produzca c en todas las entradas, porque no puede escribir ningún cs. Solo puede expresar todas las funciones computables en entradas y salidas codificadas como cadenas de as y bs.

Por lo tanto, no es cierto que todos los lenguajes completos de Turing puedan calcular las mismas cosas, ni siquiera cuando limitamos estas cosas para que sean las funciones computables de sus entradas potenciales a sus salidas potenciales. El lenguaje puede requerir que las entradas y salidas se codifiquen de ciertas maneras.

reinierpost
fuente