Siendo de Física, he sido entrenado para investigar muchos problemas desde un punto de vista geométrico. Por ejemplo, la geometría diferencial de múltiples en sistemas dinámicos, etc. Cuando leo los fundamentos de la informática, siempre trato de encontrar interpretaciones geométricas. Como una...
Si es el conjunto de tiempos de detención de máquinas Turing de estado en un alfabeto binario con cinta inicial vacía, entonces .n B B ( n ) = máx. H T ( n )HT(n)HT(n)HT(n)nnnBB(n)=maxHT(n)BB(n)=maxHT(n)BB(n) = \max HT(n) ¿Qué podemos decir sobre el segundo número más grande en HT(n)HT(n)HT(n) ?...
¿Es posible construir una implementación mecánica de un solo propósito (no completa de Turing) de, por ejemplo, Microsoft Word? ¿Es posible implementar cosas como iteradores, funciones de primer orden, toda la gama de técnicas de programación? ¿Podrían los engranajes y otras partes mecánicas...
La forma habitual de demostrar la indecidibilidad es mediante la reducción de un problema RE-completo, como el problema de detención, la validez en la lógica de primer orden, la satisfacción de las ecuaciones de diofantina, etc. Se sabe que hay problemas recursivamente enumerables, pero...
Según tengo entendido, una prueba de que P = NP o P ≠ NP debería ser no relativizable (como en los oráculos de la teoría de la recursión). Sin embargo, prácticamente todas las pruebas parecen ser relativizables. ¿Cuáles son buenos ejemplos de pruebas no relativizables, del tipo que una prueba P =...
¿Hay problemas decidibles de tal manera que para ningún algoritmo que resuelva el problema podamos dar un límite de tiempo en función de la longitud n de la instancia de entrada? Llegué a esta pregunta porque estaba pensando en lo siguiente: Supongamos que tenemos un problema recursivamente...
Es bien sabido que el problema de detención es indiscutible. Sin embargo, es posible "comprimir" exponencialmente la información sobre el problema de detención, de modo que descomprimirla sea computable. Más precisamente, es posible calcular a partir de una descripción de máquinas de Turing y un...
El papel Lauri Hella y José María Turull-Torres, Cálculo de consultas con lógicas de orden superior , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 propone lógica VO, lógica de orden variable. Esto permite la cuantificación sobre los pedidos sobre las variables. VO es bastante...
Por lo general, es más simple razonar sobre el cálculo donde la limitación es la finitud de la computación en lugar de un umbral como "computable en una cantidad de tiempo polinómica". En la teoría de los lenguajes formales, por ejemplo, en lugar de usar para caracterizar un monoïd aperiódico, es...
¿Cuál es el modelo computacional más simple para el cual el problema del vacío es indecidible? El problema de vacío para un modelo computacional (por ejemplo, autómata de estado finito, autómata de empuje alternativo, autómata cuántico de error acotado con un contador, LBA determinista, etc.) es...
Probablemente esto sea bastante simple, pero considere el problema estándar de correspondencia posterior: Dado y β 1 , ... , β N , encuentre una secuencia de índices i 1 , ... , i k tal que alpha i 1 ⋯ α i K = β i 1 ⋯ β i K . Esto es, por supuesto, indecidible.α1, ... , αnorteα1,…,αN\alpha_1,...
He estado tratando de entender qué, por qué y cómo del cálculo pero no puedo entender "¿por qué funciona?"λλ\lambda "Intuitivamente" obtengo el modelo de computabilidad de Turing Machines (TM). Pero esta abstracción me deja confundido.λλ\lambda Supongamos que las TM no existen; entonces, ¿cómo...
Deje que los términos sizesizesize de λλ\lambda se definan de la siguiente manera: size(x)=1size(x)=1size(x) = 1 , size(λx.t)=size(t)+1size(λx.t)=size(t)+1size(λx.t) = size(t) + 1 , size(ts)=size(t)+size(s)+1size(ts)=size(t)+size(s)+1size(t s) = size(t) + size(s) + 1 . Deje que la complejidad...
Podemos pensar en la complejidad de Kolmogorov de una cadena xxx como la longitud del programa más corto PPPy la entrada yyy tal que x=P(y)x=P(y)x = P(y) . Por lo general, estos programas se extraen de un conjunto completo de Turing (como PPP podría ser la descripción de una máquina de Turing, o...
El "nombre del juego de mayor número" le pide a dos jugadores que escriban un número en secreto, y el ganador es la persona que anotó el número mayor. El juego comúnmente permite a los jugadores escribir funciones evaluadas en un punto, por lo que también sería una cosa aceptable para...
Como sabemos, la definición de la complejidad computacional del algoritmo es casi sin controversia, pero la definición de la complejidad computacional de los reales o los modelos de cálculo sobre los reales no es en tal caso. Conocemos el modelo y modelo de Blum y Smales en el libro Análisis...
¿Existe una forma documentada de calcular nudos? (circunferencias incrustadas en un espacio euclidiano tridimensional). Quiero decir, un tipo de datos para representarlos y un algoritmo para determinar si dos instancias del tipo de datos representan el mismo nudo. Si la respuesta es positiva,...
El siguiente problema es decidible: Dada una gramática libre de contexto , ¿es L ( G ) = ∅ ?solGGL(G)=∅L(G)=∅L(G) = \varnothing El siguiente problema es indecidible: Dada una gramática libre de contexto , ¿es L ( G ) = A ∗ ?GGGL(G)=A∗L(G)=A∗L(G) = A^{\ast} ¿Existe una caracterización de...
¿Es posible construir un algoritmo que tome como entrada un autómata pushdown junto con la promesa de que el lenguaje aceptado por este autómata L ( M ) es un lenguaje determinista libre de contexto y genera un autómata determinista pushdown N que acepta exactamente el lenguaje aceptado por M...
Sé que la pregunta "si una fórmula de primer orden tiene un modelo" es indecidible en general.ϕϕ\phi ¿Alguien podría darme un enlace o un libro que dé la respuesta para modelos finitos? Si tengo una fórmula de primer orden , ¿es decidible si ϕ tiene un modelo finito? Estoy bastante seguro de que...