¿Pueden existir este tipo de programas en cada idioma de Turing completo?

En todos los idiomas Turing completo, es posible crear un compilador¿Pueden existir este tipo de programas en cada idioma de Turing completo?

trabajar por sí mismo que por primera vez se ejecuta en un intérprete escrito en algún otro idioma y luego compila su propio código fuente? (Bootstrapping)
compilador C++ compilador de normas que genera binarios para, por ejemplo: Windows?
Regex Analizador y Evaluater?
World of Warcraft clone? (Suponiendo que la lengua se pone los enlaces API necesarias como, por ejemplo, OpenGL y el código fuente de WoW está disponible)

(Todo aquí teórico)

Tomemos Brainf * ck como lengua ejemplo.

Fuente

2010-04-08 I can' t tell you my name.

estoy actualmente implementando un clon de WoW usando sed, estoy buscando algunos desarrolladores interesados – LB40

sonidos divertidos en la medida de como puedo decir (Realmente no sé sed) Si cambias al ensamblador 8086, estoy en: P –

Supongo que tú ¿un intérprete o un ejecutivo, ya que un compilador es un concepto dependiente de la arquitectura VonNuemann? – RBarryYoung

Sí, por supuesto, todos esos. Eso es lo que significa "Turing-completo", después de todo: puede calcular todo lo que se puede calcular.

Fuente

2010-04-08 15:16:40

No puedo encontrar una referencia que respalde esto en este momento, pero IIRC es una pregunta abierta si hay o no problemas computables que no pueden ser resueltos por una máquina de turing. Creo que esto se debe principalmente a una definición nebulosa de lo que realmente significa "computable". – rmeador

@rmeador Turing inventó su máquina idealizada precisamente para poder razonar acerca de lo que es y no es computable. El documento que introdujo el concepto de MT se llamaba "Números computables ..." –

@Neil Butterworth, pero el trabajo de Turing sobre computabilidad implica un aspecto de "agitar la mano", en el sentido de * supone * que cualquier cosa computable puede ser calculada por una máquina de Turing, o equivalentemente, * define * un algoritmo computable como uno para el cual existe un programa de máquina de Turing. El trabajo de Kleene y Church es equivalente, y como dijo Kleene, es un tanto vago e intuitivo. –

Cualquier algoritmo que se pueda implementar en un idioma de Turing-Complete se puede implementar en cualquier otro. Sus preguntas tienen más que ver con los servicios del sistema operativo y las API que deben estar disponibles a través del idioma en cuestión.

En resumen, la respuesta es sí a todo lo anterior desde el punto de vista del lenguaje formal.

Fuente

2010-04-08 15:18:14 rixin

En todos los idiomas Turing completo, es posible la creación de un trabajo ...

Si el lenguaje de un Turing completo puede hacerlo, entonces todos podemos. En este sentido, todos son igualmente "poderosos". Como todo lo que describió ya existe en al menos un idioma de Turing completo, cualquiera de estos programas puede escribirse en cualquier otro idioma de Turing completo.

Sin embargo, el mero hecho de que algo es posible no quiere decir que sea fácil , o incluso factible . Esa es una distinción muy importante, y es el quid de por qué existen diferentes lenguajes de programación. No todos son igualmente buenos para hacer tipos específicos de software; si lo fueran, ¡solo necesitaríamos un idioma!

Fuente

2010-04-08 15:19:15

no veo por qué podría no ser factible, si es posible, ¿no significa eso que es factible? Tienes un ejemplo ? – LB40

@John +1. P: ¿Por qué hay más de una base de datos? R: Porque todos apestan. –

@LB: la posibilidad no es igual a la viabilidad. Aquí hay un ejemplo trivial. Imagine un lenguaje completo de Turing en el que escribir la instrucción "asignar valor x al símbolo y" requiere más memoria que la que existe en todo el mundo. Tal lenguaje hace que sea posible escribir programas de Turing, pero no es posible escribirlos porque no es práctico codificar realmente la información que desea. –

Teórico, sí. Pero una pregunta mucho más interesante es si sería prácticamente posible dado un cierto lenguaje de programación "esotérico".

Fuente

2010-04-08 15:19:16 JesperE

-2

Todos los lenguajes de Turing-Complete pueden calcular el mismo conjunto de funciones. Por lo tanto, un lenguaje completo puede hacer todo lo que usted escribió porque eso se calcula con otros lenguajes completos de turing.

Fuente

2010-04-08 15:19:47

Todo lo que realmente requiere Turing-complete es que puede hacer cálculos simples, tener algunas variables y hacer un ciclo while. O cualquier cantidad de cosas equivalentes. Si desea hacer programas reales, necesita un poco más (especialmente llamadas de sistema) y también debe preocuparse por la eficiencia (las máquinas de turing pueden ser muy lentas ...) En teoría, no hay diferencia entre los sistemas equivalentes de turing, pero en la práctica sí lo hay.

Si alguien tiene un cliente de WoW en BF, estaré muy impresionado!

Fuente

2010-04-08 15:25:52

Turing completo solamente expresar capacidad de cómputo, nada de E/S capacidad!

Fuente

2010-04-08 18:38:28 Rhangaun

StackOverflow típico: las respuestas incorrectas se votan sin pensar y las únicas respuestas correctas languidecen en la oscuridad. – RBarryYoung

No, la integridad de Turing no tiene nada que ver con E/S y hardwares. Sin embargo, puede pretender que existan E/S, sistemas de hardware y sistemas gráficos mediante el uso de variables (o la "cinta de memoria"). En BF, podría usar las 2 primeras células (x, Y) para el "pretendido" resolución de la pantalla, luego otros x veces y células para todos los píxeles en la pantalla, entonces la próxima celda (n) para la "pretendida" tamaño del sistema de archivos, a continuación, junto n células para el sistema de archivos de contenido ...

Fuente

2010-04-09 01:37:35

La primera respuesta correcta que he visto aquí. – RBarryYoung

¿Pueden existir este tipo de programas en cada idioma de Turing completo?

Respuesta

Cuestiones relacionadas