Preguntas sobre las máquinas de Turing, un modelo teórico de computación mecánica capaz de simular cualquier programa de computadora.
Soy un estudiante universitario de CS. Entiendo cómo se le ocurrió a Turing su máquina abstracta (modelar a una persona haciendo un cálculo), pero me parece una abstracción incómoda y poco elegante. ¿Por qué consideramos una "cinta" y una cabeza de máquina que escribe símbolos, cambia de estado y...
Sabemos que el problema de detención (en máquinas de Turing) es indecidible para las máquinas de Turing. ¿Hay alguna investigación sobre qué tan bien la mente humana puede manejar este problema, posiblemente ayudado por las máquinas de Turing o las computadoras de uso general? Nota : Obviamente,...
¿Existe un conjunto de construcciones de lenguaje de programación en un lenguaje de programación para que pueda considerarse Turing Complete? Por lo que puedo decir de Wikipedia , el lenguaje debe admitir la recursividad o, al parecer, debe poder ejecutarse sin detenerse. ¿Es esto todo lo que hay...
Estoy de acuerdo en que una máquina de Turing puede resolver "todos los posibles problemas matemáticos". Pero eso se debe a que es solo una representación de la máquina de un algoritmo: primero haga esto, luego haga eso, finalmente obtenga eso. Quiero decir que cualquier cosa que sea solucionable...
En computación cuántica, ¿cuál es el modelo equivalente de una máquina de Turing? Para mí está bastante claro cómo los circuitos cuánticos pueden construirse a partir de puertas cuánticas, pero ¿cómo podemos definir una máquina cuántica de Turing (QTM) que realmente pueda beneficiarse de los...
En esta respuesta se menciona Un lenguaje normal puede ser reconocido por un autómata finito. Un lenguaje sin contexto requiere una pila, y un lenguaje sensible al contexto requiere dos pilas (lo que equivale a decir que requiere una máquina Turing completa) . Quería saber sobre la verdad de...
¿Hay máquinas teóricas que excedan la capacidad de las máquinas de Turing en al menos algunas
Veo que la mayoría de las definiciones de lo que es ser Turing completo son tautológicas hasta cierto punto. Por ejemplo, si buscas en Google "qué significa ser Turing completo", obtienes: Una computadora está completa en Turing si puede resolver cualquier problema que una máquina de Turing...
Alan Turing propuso un modelo para una máquina (Turing Machine, TM) que computa (números, funciones, etc.) y demostró el Teorema de detención . Un TM es un concepto abstracto de una máquina (o motor si lo desea). El teorema de detención es un resultado imposible. Un Carnot Engine (CE) es un...
Estaba pasando por la discusión sobre la pregunta ¿Cómo definir las máquinas cuánticas de Turing? y siento que la TM cuántica y la TM no determinista son lo mismo. Las respuestas a la otra pregunta no tocan eso. ¿Son estos dos modelos uno y el mismo? Si no, ¿Cuáles son las diferencias entre...
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...
Actualmente estoy leyendo un libro sobre algoritmos y complejidad. En este momento, estoy leyendo sobre funciones computables y no computables, y mi libro dice que hay muchas más funciones que no son computables que computables, de hecho, la mayoría no son computables, dice. En cierto sentido,...
Encontré a continuación la declaración de Alan M. Turing aquí : "La opinión de que las máquinas no pueden dar lugar a sorpresas se debe, creo, a una falacia a la que los filósofos y matemáticos están particularmente sujetos. Esta es la suposición de que tan pronto como se presenta un hecho a la...
Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...
El problema de detención indica que no existe un algoritmo que determine si un programa determinado se detiene. Como consecuencia, debe haber programas sobre los que no podemos saber si terminan o no. ¿Cuáles son los ejemplos más simples (más pequeños) conocidos de tales
Estoy haciendo una presentación sobre las máquinas Turing y quería dar algunos antecedentes sobre los FSM antes de presentar las máquinas Turing. El problema es que realmente no sé qué es MUY diferente el uno del otro. Esto es lo que sé que es diferente: FSM tiene estados secuenciales...
Recientemente en mi clase de CS me presentaron a la máquina de Turing. Después de la clase, pasé más de 2 horas tratando de averiguar cuál es la relación entre una cinta y una máquina. No conocía por completo la existencia de cintas de computadora o cómo interactuaban las cintas y las máquinas...
Soy ingeniero eléctrico, y solo tuve un curso de CS en la universidad hace 26 años. Sin embargo, también soy un usuario devoto de Mathematica. Tengo la sensación de que las máquinas de Turing son muy importantes en informática. ¿Es la importancia solo en la teoría de la informática? Si hay...
Considerando solo el alfabeto , las cadenas que se pueden dar como entrada a las máquinas de Turing son del conjunto Σ ∗ . Pero, ¿tiene sentido que la entrada sea una cadena binaria infinita? Por ejemplo, si una máquina de Turing acepta todas las cadenas que comienzan con un 0, ¿una cadena binaria...
Tengo problemas para comprender la prueba de la indecidibilidad del problema de detención. Si devuelve si el programa a se detiene o no en la entrada b , ¿por qué tenemos que pasar el código de P para a y b ?H( a , b )H(a,b)H(a,b)unaaasibbPAGSPPunaaasibb ¿Por qué no podemos alimentar con P y...