Después de leer una pregunta relacionada , acerca de las pruebas de algoritmos de existencia no constructivas, me preguntaba si existen métodos para mostrar la existencia de máquinas de cómputo "pequeñas" (por ejemplo, a nivel de estado) sin construirlas realmente. Formalmente: supongamos que...
Estoy buscando un lenguaje pequeño que ayude a 'convencer' a los estudiantes de que las máquinas de Turing son un modelo informático suficientemente general. Es decir, un lenguaje que se parece a los idiomas a los que están acostumbrados, pero que también es fácil de simular en una máquina de...
Respuesta: no conocida Muchas gracias a todos los que ayudaron a refinar esta pregunta y las definiciones asociadas. Las definiciones de esta wiki proporcionaron el punto de partida para la wiki TCS más reciente " ¿Contiene P lenguajes cuya existencia es independiente de PA o ZFC? (Wiki de la...
Robin Gandy fue alumno de Alan Turing . Gandy hizo un análisis del motor analítico de Babbage (ver 'Gandy - La confluencia de ideas en 1936' citado en 'Herken, Rolf - La máquina universal de Turing: una encuesta de medio siglo . Springer Verlag') - y dijo que sí (cf. p. 52–53): Las funciones...
Para celebrar el cumpleaños de Alan Turing, Google publicó un garabato que muestra una máquina. ¿Qué tipo de máquina es el garabato? ¿Puede expresar un lenguaje completo de Turing? Hay diferencias obvias en la máquina clásica de turing: una cinta finita, restricciones en cómo se puede conectar el...
Soy un estudiante de maestría enfocado en sistemas distribuidos pero también interesado en informática teórica. Me preguntaba si hay una representación formal de un sistema distribuido encima de una máquina de turing. Es decir, ¿es posible extender (hacer una variante) el concepto de una máquina de...
Estaba jugando con la muy interesante y abierta pregunta " Alfabeto de la máquina de Turing de una sola cinta " (por Emanuele Viola) y se me ocurrió el siguiente idioma: L = { x ∈ { 0 , 1 }norte st | x | = n = 2metro y c o u n t 1 ( x ) = k ∗ m ;n , m , k ≥ 1
La mayor parte de la literatura parece estar relacionada con máquinas con oráculos individuales para problemas específicos, sin embargo, parece haber algunos documentos que consideran máquinas con oráculos múltiples. ¿Existe un buen trabajo o tesis que proporcione una visión general de lo que se...
¿Los autómatas con límites lineales no deterministas de visita limitada reconocen solo los lenguajes normales? Por un autómata lineal no determinista (nLBA) me refiero a una máquina de Turing no determinista de una sola cinta donde la entrada viene "rellenada" con marcadores en ambos extremos que...
Arreglemos una codificación de máquinas de Turing y una máquina universal de Turing, U, que en la entrada (T, x) emite cualquier salida de T en la entrada x (posiblemente ambas funcionando para siempre). Defina la complejidad de Kolmogorov de x, K (x), como la longitud del programa más corto, p, de...
Tengo una pregunta ingenua: ¿existe una máquina de Turing cuya terminación sea verdadera pero no demostrable por ninguna teoría natural, consistente y finitamente axiomatizable? Pido una mera prueba de existencia en lugar de un ejemplo específico. Esto podría tener alguna conexión con el análisis...
un tiempo he sentido curiosidad por las máquinas de Turing con exactamente una cinta y exactamente 3 estados (es decir, el estado inicial , el estado de aceptación y el estado de rechazo ). Tenga en cuenta que permito alfabetos de cinta arbitrarios (finitos) (es decir, el alfabeto de cinta no está...
Estoy buscando escribir una encuesta sobre el método de representar la dinámica de la computación basada en el estado en el marco de las coalgebras. Hasta ahora, he logrado encontrar documentos sobre representaciones de coalgebra de DFA, NFA, máquinas Mealy, máquinas Moore, gramáticas libres de...
¿Existe una generalización del juego GO que se sabe que está completa? En caso negativo, ¿tiene alguna sugerencia sobre reglas razonables (de generalización) que puedan usarse para tratar de demostrar que está completa? La obvia es que el juego debe jugarse en un tablero infinito (cuadrante...