La tesis de Church-Turing establece que todo lo que se puede calcular físicamente, se puede calcular en una máquina de Turing. El documento "Computación analógica a través de redes neuronales" (Siegelmannn y Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) afirma que una red...
Esta es una pregunta ingenua y, por lo tanto, posiblemente malformada, ¡disculpas de antemano! Mi opinión es que una máquina de Turing puede verse como la base computacional para los lenguajes de programación de procedimientos / imperativos. Del mismo modo, el cálculo lambda es la base de los...
Hay muchos (y quiero decir muchos) idiomas contables que son decidibles por Turing. ¿Puede cualquier lenguaje incontable ser Turing
Hay tiempos espaciales relativistas (por ejemplo, tiempos espaciales MH; ver Hogarth 1994) donde una línea mundial de duración infinita puede estar contenida en el pasado de un observador finito. Esto significa que un observador normal puede tener acceso a un número infinito de pasos de...
Si tenemos algún programa de computadora arbitrario que pueda modificar sus instrucciones, ¿es posible simular ese programa con un programa que no pueda modificar sus instrucciones? Editar: Soy nuevo en stackexchange, así que no estoy seguro si se me permite hacer una NUEVA pregunta aquí, pero...
He visto sitios web que pretenden "probar" que HTML5 + CSS es Turing Complete. He visto sitios web que pretenden "probar" que SQL está Turing completo. He visto un montón de sitios web que pretenden "explicar" lo que significa ser Turing completo. ¡Suficiente! ¿Dónde puedo encontrar un libro?...
Quisiera citar a Nielsen & Chuang, Computación Cuántica e Información Cuántica, edición del décimo aniversario, página 5 (énfasis mío): Una clase de desafíos para la fuerte tesis de Iglesia-Turing proviene del campo de la computación analógica. En los años posteriores a Turing, muchos...
Según la tesis de Church-Turing, es imposible diseñar un algoritmo para decidir el problema de detención. ¿La palabra algoritmo en este contexto incluye inteligencia artificial o no, es decir, la tesis de Church-Turing también se aplica a la inteligencia artificial? ¿Es posible diseñar un...
Cuando leí sobre la tesis de la Iglesia-Turing, parece ser una afirmación común de que "la realidad física es computable por Turing". ¿Cuál es la base de este reclamo? ¿Hay algún resultado teórico en este sentido? Por contexto, soy un investigador que trabaja en simulaciones físicas, así que, por...
En primer lugar, me disculpo si se me ha preguntado esto, pero realmente no encontré nada. Me he topado con este artículo . Dice que hay un problema que solo las computadoras cuánticas pueden resolver. Según tengo entendido, esto debería significar, intuitivamente, que este problema es...