¿Puede un idioma ser completo pero incompleto de otras maneras?

Question

Por ejemplo, ¿hay ciertas cosas al escribir un sistema operativo que no se pueden lograr en un lenguaje completo?

Answer 1

No. o al menos si encontró una que sería una refutación del Church Turing Thesis.

Sin embargo, hay lenguajes que están completos pero en los que es un completo dolor de cabeza escribir ciertos programas, es decir, procesamiento de cadenas en FORTRAN, programación numérica en COBOL, aritmética entera en sed, prácticamente todo en x86 ensamblador.

Y luego, por supuesto, está brainfuck.

Answer 2

Sí, puede tener un idioma que no le permita manipular el hardware directamente. Sería difícil escribir un sistema operativo utilizando el shell Bourne, por ejemplo. Pero estas limitaciones son menores de lo que piensas. Los sistemas operativos se han escrito en Standard ML, Scheme e incluso en Haskell.

Answer 3

Turing-complete es la definición formal más general de integridad. Existen características de idioma que son necesarias para ciertas aplicaciones, pero que no se ajustan a las definiciones formales.

Por ejemplo, las capacidades gráficas, la capacidad de engendrar procesos en segundo plano, la capacidad de persistir y la capacidad de conectarse a la red son funciones útiles, pero no se relacionan con la integridad completa de un idioma. Por lo tanto, Python en Google App Engine o un applet de Java que se ejecuta en un sandbox todavía es Turing-complete.

Observará que, en muchos casos, este tipo de funciones las proporcionan las bibliotecas, en lugar del lenguaje central.

Answer 4

Si habla de pragmática, entonces ... puede imaginarse un lenguaje de programación sin capacidad para leer o escribir archivos (por ejemplo, un lenguaje que puede calcular cualquier función en enteros, pero eso es todo) ... Solo porque un idioma no pueda operar mi tostadora no significa que no sea Turing-completo, pero sí significa que hay cosas que no puede hacer, así que no estoy seguro de qué tan importante o útil sea esta distinción.

Answer 5

El lenguaje puede o no puede hacer cosas como: subrutinas, recursividad, tipos de datos personalizados, bucles, definición de clases, goto, etc. El conjunto de características del lenguaje lo hace completo o no. Por ejemplo, el idioma está incompleto si no tiene bucles, gotos y subrutinas; no puede realizar ninguna operación cíclica. La integridad del lenguaje es algo muy teórico y científico. Como, por ejemplo, está comprobado que incluso si su idioma no permite llamar funciones recursivamente, sino que permite indicadores de función: puede simular recursividad, es decir, con y-combinator.

Cosas como trabajar con archivos y hardware muy a menudo no es parte del lenguaje. Para realizar cualquier tarea de programación necesita más que lenguaje. Necesita un entorno en el que su programa trabaje. En x86 como idioma, tiene la instrucción "int" con un solo parámetro, pero corresponde al sistema operativo realizar ciertas operaciones cuando ejecuta "int 21h".

El lenguaje solo necesita alguna forma de comunicarse con el entorno y estar completo, entonces depende del entorno trabajar con él. Es válido escribir en x86 asm "mov ax, bx" pero depende de su CPU realizar esta operación.

Al estar incompleto de alguna otra manera, es fácil, solo defina su propia versión de integridad. es decir, odio trabajar sin un POO basado en clases, así que definamos que el lenguaje no es Feldman: completo si no tiene características de lenguaje que admitan POO basado en clases. Ok, entonces, C y Javascript no son F-completos.Todavía puede hacer cualquier cosa en esos idiomas e incluso simular OOP basado en clases a algún nivel.

En cuanto al sistema operativo, aún necesita un procesador que ejecute las instrucciones y el compilador que traduce el idioma a las instrucciones de la CPU. Puedo imaginar al compilador traduciendo cualquier cosa a los códigos de las máquinas. Al igual, que sigue es válido código JS

for(var i=0;i<10;i++){ 
mov("ax",i); 
int(0x21); 
} 

y no debería ser tan difícil compilar a código máquina.

En el mundo moderno usted elige no solo el idioma, también elije plataformas, bibliotecas estándar y no estándar, literatura, comunidad, soporte, etc. Todas esas cosas afectan su capacidad para hacer ciertas cosas, y pueden tomarse en conjunto. o puede no ser "lo suficientemente completo" para su tarea. Pero si no puedo compilar el código de C++ en el applet de Java, no significa que sea un lenguaje incompleto de C++. Es solo la ausencia de un compilador que transformará el código de C++ en algo que pueda ser cargado por JVM.

Si lo desea, puede diseñar un lenguaje con características de idioma como "OpenFile, PingNetworkHost, DownloadMpeg4FileOverHttpsAndPlayBackwards". Pero si el lenguaje no los tiene, aún se pueden implementar con otras características de idioma y compatibilidad con el entorno, por lo que la ausencia de dichas características no hace que el lenguaje sea incompleto. Si su idioma es como C pero sin operador de goto, operador de bucle (para, mientras, mientras) y funciones, entonces no puede escribir un programa cíclico y no hay ambiente y las bibliotecas pueden ayudarlo.

Answer 6

Dependiendo del contexto, "lograr algo en un idioma" significa diferentes cosas para diferentes personas. Turing es una de esas personas, y definió con mucha precisión lo que quiere decir con "completo".

Si un lenguaje (o una máquina teórica) es Turing completo, no hay cálculos de Turing que no pueda hacer. Esto no implica que el lenguaje sea omnipotente, solo que es bueno en sumas. Hay muchas "cosas" que no son cálculos de Turing, y que, por lo tanto, una computadora completa de Turing puede no ser capaz de hacer.

"Ser un sistema operativo" no es un cálculo de Turing. Para ser un sistema operativo, necesita hacer más cosas que solo cálculos. También necesita manipular hardware.

Dado un lenguaje completo de Turing, junto con un conjunto de operaciones para realizar toda la manipulación de hardware que necesita, incluido un concepto adecuado de entrada y de tiempo, puede escribir un sistema operativo. O debería decir que es posible escribir un SO. Si usted puede hacerlo personalmente, depende de cuán fácil es trabajar con el lenguaje y de las limitaciones físicas que la definición de Turing ignora, como por ejemplo si el programa resultante realmente encajará y se ejecutará en la memoria del dispositivo que desea que funcione, y corre en un tiempo realista.

Ignorando las limitaciones prácticas, sí, puede escribir un sistema operativo en cualquier idioma completo de Turing, siempre que el idioma también tenga suficientes operaciones para conducir el hardware. "Llamadas de biblioteca", si desea tomar el enfoque práctico de CS para distinguir el idioma de las bibliotecas. Turing no hizo tal distinción, porque su modelo de computación no tiene el concepto de una "llamada" de todos modos. También debe resolver el problema de arranque: su hardware debe ejecutar directamente el idioma en el que está escribiendo, o si no necesita un compilador en un idioma que el hardware ejecuta, o necesita un intérprete escrito en un idioma que el el hardware se ejecuta Una vez más, Turing ignora todo esto porque su modelo de computación usa hardware abstracto, mientras que escribir un SO es todo sobre el hardware.

En inglés (en lugar de CompSciSpeak) es común decir que un idioma "carece de ciertas características", y podría decirse que, por lo tanto, "no es completo" en comparación con otro idioma que los tenga. Uno podría contraargumentar que es posible implementar cierres en C.Uno puede, por ejemplo, escribir un programa en C que es un intérprete Lisp e insertar en él un programa Lisp como una cadena. Voila, cierres en C. Sin embargo, esto no es lo que la mayoría de las personas está preguntando si dicen: "Ojalá C tuviera cierres". Si crees que todos los idiomas necesitan cierres, entonces C está incompleto. Si cree que cada idioma necesita programación estructurada, entonces el ensamblador ARM está incompleto. Si crees que debería ser posible agregar métodos dinámicamente a un objeto, entonces C++ es incompleto, aunque es perfectamente posible escribir una clase C++ con los métodos "AddMethod" y "CallMethodByName" y falsificar tu propia convención de llamadas desde allí. Y así.

Turing no cree que los idiomas necesiten ninguno de estos servicios: no afectan los cálculos que se pueden realizar, lo fácil que es escribir ciertos programas. El concepto de integridad de Turing no tiene nada que decir sobre cómo se ven los programas, o cómo están organizados, solo lo que producen. Entonces esos lenguajes están completos, pero desde el punto de vista del programador hay ciertas cosas que no se pueden lograr en esos idiomas.

Answer 7

usabilidad incompleto :)

Answer 8

La respuesta es un sí más definida. La integridad de Turing solo implica que se puede usar un lenguaje completo de Turing para calcular cualquier función computable. Por un lado, no dice nada acerca de la complejidad de un cálculo.

Por lo general, puede esperar que cualquier algoritmo de tiempo polinomial se pueda expresar como un algoritmo de tiempo polinomial en cualquier otro lenguaje completo de Turing, pero eso es todo. Especialmente cualquier requisito de tiempo real (suave o difícil) sale de la ventana, si su único enfoque es la integridad de Turing.

Otra cosa importante es la expresividad de un idioma, que en gran medida es una propiedad subjetiva, pero se puede apreciar que los programas son mucho más difíciles de escribir en cualquier código de máquina que, por ejemplo, Java.

En cuanto a los sistemas operativos, una interfaz para el hardware es imprescindible, pero cualquier lenguaje puede ser provisto de tales utilidades.

[Editar] Otra cosa que podría agregar es que ninguna implementación real de ningún lenguaje de programación es completa por la naturaleza de nuestras máquinas de computación finita. Si bien la tesis Church-Turing, junto con los descubrimientos seminales relacionados (como el problema de la detención), sientan las bases de nuestra comprensión de la informática, raramente se encuentran con el mundo de la informática práctica.

Answer 9

Cuando se habla de idiomas, generalmente se supone que los idiomas se ejecutan en algunas máquinas muy simples. Como tal, cualquier concepto de leer desde un archivo o acceder a la red normalmente no se considera en relación con el poder de un idioma.

Hay diferentes clases de idiomas que se utilizan a menudo en la teoría de la computabilidad (cada uno con casi infinitas modificaciones)

1. autómata finito. Esta es la clase más simple de máquinas y pueden reconocer la clase más pequeña de idiomas, que es exactamente los idiomas que las expresiones regulares pueden reconocer, es decir. si una cadena comienza con dos 'a's y termina con d. No se pueden usar para reconocer si una cadena contiene un conjunto equilibrado de paréntesis, fx.
2. Push down autómata. Esto es esencialmente una extensión de autómatas finitos con una pila. A diferencia de las máquinas de estado finito, se pueden usar para decir si una cadena en particular contiene un conjunto equilibrado de paréntesis. Los lenguajes que presionan los autómatas pueden reconocer exactamente el el conjunto que se puede describir usando gramáticas libres de contexto y se usan a menudo para analizar el código fuente.
3. Turing Machines. Estas son las máquinas más potentes de la clase aquí, pero eso no significa que puedan usarse para responder todas las preguntas. Son incapaces de responder la pregunta: ¿esta cuerda describe una máquina de Turing que funcionará para siempre? De hecho, cualquier máquina de Turing no puede decir nada sobre las propiedades no triviales de cualquier máquina de Turing (Teorema del Arroz).

Así que sí una máquina de Turing tiene limitaciones, y hay clases de máquinas que pueden hacer algo una máquina de Turing no puede, pero tienen (todo con toda probabilidad) sólo ha existido en teoría, más nuevo en la práctica.

Answer 10

No creo que las definiciones de integridad distintas de Turing (o expresiones regulares, o autómatas push-down) sean relevantes para idiomas. Pero esta completitud es solo con respecto a las instalaciones computacionales numéricas o simbólicas.

Parece que las cosas que menciona son más una función del entorno de ejecución y el entorno que el idioma. Hay una distinción importante, y las nociones formales de integridad generalmente solo se aplican a los idiomas mismos.