Estoy tratando de encontrar las respuestas de dos preguntas sobre la máquina Universal Turing. ¿Cómo puede la máquina Universal Turing simular una máquina Turing si la que se está simulando tiene un mayor número de estados? ¿Cómo puede la máquina de Turing universal simular una máquina de Turing...
Este es probablemente un pensamiento tonto, pero supongamos que tenemos una computadora que está programada para realizar una secuencia infinita de cálculos y supongamos que el cálculo de tarda segundos en completarse. Entonces esta computadora puede hacer un número infinito de cálculos en un...
He estado tratando de averiguar si el problema de detención es decidible para autómatas celulares unidimensionales de 3 símbolos. Definición Sea la configuración del sistema en el paso de tiempo . Más formalmente , donde es el alfabeto.i f : A ∗ × N → A ∗
Hoy he aprendido que el análisis de algoritmos difiere según el modelo computacional. Es algo en lo que nunca he pensado ni oído hablar. Un ejemplo que me dio, que lo ilustró aún más, por el usuario @chi fue: Por ejemplo, considere la tarea: dado devuelve . En RAM esto se puede resolver...
A mitad de período había una variante de la siguiente pregunta: Para un decidible, defina Pref ( L ) = { x ∣ ∃ y st x y ∈ L } Muestre que Pref ( L ) no es necesariamente decidible.LLLPref ( L ) = { x ∣ ∃ y st x y∈ L }Pref(L)={x∣∃y s.t. xy∈L}\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. }...
¿Es una máquina de Turing que puede leer y escribir símbolos de un alfabeto infinito más poderosa que una TM normal (esa es la única diferencia, la máquina todavía tiene un número finito de estados)? La intuición me dice que no, ya que necesitas un número infinito de estados para diferenciar cada...
¿Por qué los números computables (en el sentido de Turing) son enumerables? Debe ser muy obvio, pero actualmente no lo estoy
Queremos en mosaico -square usando dos tipos de mosaicos: -square tile y -square tile de modo que cada cuadrado subyacente se cubra sin superponerse. Definamos una función que proporcione el tamaño del cuadrado más grande que se puede labrar usando cuadrados y cualquier número de cuadrados.1 × 1 2...
Al leer esta pregunta " Problemas naturales indecidibles de RE pero no completos de Turing ", me vino a la mente el siguiente lenguaje: Si es la función de castor ocupado (puntaje máximo alcanzable entre todas las máquinas Turing de 2 símbolos de estado n detenidas del tipo descrito anteriormente,...
He estado leyendo algunos documentos de teoría del lenguaje formal y me he encontrado con un término que no entiendo. El documento a menudo se referirá a un conjunto que está "efectivamente cerrado bajo intersección" u otras operaciones. ¿Qué significa "efectivamente" aquí? ¿Cómo difiere esto del...
Soy un estudiante universitario que recién comienza a leer sobre informática reversible. Sé que, debido al principio de Landauer, los cálculos irreversibles disipan el calor (y los reversibles no). Lo mencioné con mi profesor, que nunca antes había oído hablar de la computación reversible, y estaba...
Recientemente hablé con un amigo sobre un sitio web que propuso desafíos de expresiones regulares, principalmente haciendo coincidir un grupo de palabras con una propiedad especial. Estaba buscando una expresión regular que coincida con cadenas como ||||||||donde el número |es primo. Inmediatamente...
Una declaración del teorema de Rice se da en la página 35 de "Complejidad computacional: un enfoque moderno" (Arora-Barak): Una función parcial de { 0 , 1 }∗{0,1}∗\{0,1\}^* a { 0 , 1 }∗{0,1}∗\{0,1\}^* es una función que no está necesariamente definida en todas sus entradas. Decimos que una TM...
Este es un seguimiento de otra pregunta aquí , y espero que no sea demasiado filosófico. Como señaló Raphael en un comentario sobre mi pregunta anterior, realmente no entiendo la definición de "computable", pero de acuerdo con algunos documentos que leí, la definición tampoco está muy clara cuando...
Supongamos que tengo dos funciones y y estoy interesado en determinar siFFFGGG F(x)=∫G(x)dx.F(x)=∫G(x)dx.F(x) = \int G(x)dx. Supongamos que mis funciones están compuestas de funciones elementales (polinomios, exponenciales, registros y funciones trigonométricas), pero no, digamos, series de...
Estoy tratando de encontrar una prueba de lo siguiente: Para cualquier idioma , existe un lenguaje de B tal que A ≤ T B pero B ≰ T A .AUNAABsiBA≤TBUNA≤TsiA \le_{\mathrm{T}} B≰TA≰TUNA\nleq_{\mathrm{T}} A Estaba pensando en dejar que sea A T M , pero me doy cuenta de que no todos los idiomas son...
Para demostrar que 3 colores es decidible, ¿es suficiente decir: Cada nodo en el gráfico tiene 3 colores posibles. Por lo tanto, podemos enumerar las posibilidades y luego verificar que no haya dos bordes conectando nodos con el mismo color3norte3norte3^n ¿Eso prueba que 3 colores es...
Hoy en el almuerzo, mencioné este problema con mis colegas, y para mi sorpresa, el argumento de Jeff E. de que el problema es decidible no los convenció ( aquí hay una publicación estrechamente relacionada sobre el desbordamiento matemático). Un enunciado del problema que es más fácil de explicar...
Se me ocurrió esta pregunta sobre el problema de detención y no pude encontrar una buena respuesta en línea, preguntándome si alguien puede ayudar. ¿Es posible que el problema de detención sea decidible para cualquier TM en cualquier entrada, siempre que la entrada no sea la propia TM?...
En este sitio hay muchas variantes sobre la cuestión de si las TM pueden decidir el problema de detención, ya sea para todas las otras TM o ciertos subconjuntos. Esta pregunta es algo diferente. Pregunta si el problema de detención se aplica a todas las TM puede ser decidido por una TM. Creo que...