¿Qué operaciones deben realizarse para realizar cualquier cálculo analógico arbitrario ? ¿Serían suficientes la suma, la resta, la multiplicación y la división? Además, ¿alguien sabe exactamente qué problemas son manejables con el cálculo analógico, pero no con el
¿Existe una máquina de Turing que se detiene en todas las entradas pero esa propiedad no es demostrable por alguna razón? Me pregunto si esta pregunta ha sido estudiada. Tenga en cuenta que "no demostrable" podría significar un sistema de prueba "limitado" (que en el sentido débil piensa que la...
Estoy empezando a leer un libro sobre Complejidad Computacional y Máquinas de Turing. Aquí está la cita: Un algoritmo (es decir, una máquina) puede representarse como una cadena de bits una vez que decidimos sobre una codificación canónica. Esta afirmación se proporciona como un hecho simple,...
En esta pregunta solo consideramos las máquinas de Turing que detienen todas las entradas. Si entonces por denotamos la máquina de Turing cuyo código es .k ∈ N k∈Nk \in \mathbb{N}T kTkT_k kkk Considere la siguiente función s ( x , y ) = min { k ∣ | L ( T k ) ∩ { x , y } | = 1...
Dados los idiomas AAA y BBB , digamos que su concatenación ABABAB es inequívoca si para todas las palabras w∈ABw∈ABw \in AB , hay exactamente una descomposición w=abw=abw = ab con a∈Aa∈Aa \in A y b∈Bb∈Bb \in B , y de lo contrario es ambigua . (No sé si hay un término establecido para esta...
Tenga en cuenta que esta es una pregunta relacionada con el estudio en un curso de CS en una universidad, NO es tarea y se puede encontrar aquí en el examen de otoño de 20112. Aquí están las dos preguntas que estoy viendo en un examen anterior. Parecen estar relacionados, el primero: Dejar...
El problema de si dos autómatas pushdown reconocen el mismo idioma es indecidible. El problema de si un autómata pushdown reconoce el idioma vacío es decidible, por lo tanto, también es decidible si reconoce un idioma finito determinado. No se puede determinar si el lenguaje aceptado por un...
No existe una solución analítica general para el problema del cuerpo n que pueda producir una función analítica que pueda usarse para proporcionar el estado de un sistema n-cuerpo en un tiempo arbitrario t con precisión exacta. Sin embargo, hay algunos casos especiales de sistemas de n cuerpos para...
Estoy usando una computadora digital para escribir este mensaje. Tal máquina tiene una propiedad que, si lo piensa, es realmente notable: es una máquina que, si se programa adecuadamente, puede realizar cualquier cálculo posible . Por supuesto, las máquinas de calcular de un tipo u otro vuelven a...
Las máquinas de mostrador con dos o más contadores suelen ser equivalentes a las máquinas de Turing en cursos sobre teoría de la computación. Sin embargo, no he visto un análisis formal de qué idiomas puede reconocer una máquina de un contador. ¿Son estos lenguajes equivalentes a los lenguajes...
¿Hay propiedades indecidibles de autómatas lineales delimitados (evitando el truco del lenguaje de conjunto vacío)? ¿Qué pasa con un autómata finito determinista? (Deje de lado la intratabilidad). Me gustaría obtener un ejemplo (si es posible) de un problema indecidible que se define sin utilizar...
En una conferencia, un profesor mencionó que las computadoras modernas no tienen tanta potencia computacional como una máquina de Turing porque no tienen memoria infinita, y dado que ninguna computadora puede tener memoria infinita, la máquina de Turing es inalcanzable y simplemente representa el...
Un conjunto es contable si tiene una biyección con los números naturales, y es computablemente enumerable (ce) si existe un algoritmo que enumera sus miembros. Cualquier conjunto enumerable computable no finito debe ser contable ya que podemos construir una biyección a partir de la...
Dado un lenguaje , defina el conjunto de longitud de L como el conjunto de longitudes de palabras en L : L S ( L ) = { | u | ∣ u ∈ L }LLLLLLLLLLS(L)={|u|∣u∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} ¿Qué conjuntos de enteros pueden ser el conjunto de longitud de un lenguaje...
Me pregunto ¿cómo es que el siguiente lenguaje está en .RR\mathrm R LMETRO1= { ⟨ M2⟩∣∣METRO2 es una TM, y L ( M1) = L ( M2) , Y | ⟨ M1⟩ | > | ⟨ M2⟩ | }LMETRO1={⟨METRO2⟩El |METRO2 es un TM, y L(METRO1)=L(METRO2), y El |⟨METRO1⟩El |>El |⟨METRO2⟩El |}L_{M_1}=\Bigl\{\langle M_2\rangle...
Tengo estas preguntas de un antiguo examen que estoy tratando de resolver. Para cada problema, la entrada es una codificación de una máquina de Turing MMM . Para un entero c>1c>1c>1 , y los siguientes tres problemas: ¿Es cierto que para cada entrada xxx , M no pasa el |x|+c|x|+c|x|+c...
Quiero saber si el siguiente problema es decidible: Instancia: un NFA A con n estados Pregunta: ¿Existe algún número primo p tal que A acepte alguna cadena de longitud p. Creo que este problema es indecidible, pero no puedo probarlo. El decisor puede tener fácilmente un algoritmo para determinar...
Idiomas como HALTTMHALTTM\text{HALT}_{TM} son RE-completeRE-complete\textsf{RE-complete} bajo muchas reducciones. Es trivial ver que co-REco-RE\text{co-RE} tiene problemas completos. S. Schmitz [1] considera algunas clases entre ELEMELEM\text{ELEM} y RECREC\text{REC} . Presentan problemas completos...
Estaba buscando problemas abiertos interesantes y fáciles de expresar en computabilidad (comprensible para estudiantes de pregrado que toman su primer curso en computabilidad) para dar ejemplos de problemas abiertos (y obviamente quiero que los estudiantes puedan entender el problema sin necesitar...
Si de hecho es igual a N P , ¿cómo mejoraría esto nuestros algoritmos para factorizar enteros más rápido? En otras palabras, ¿qué tipo de información nos daría este hecho para comprender mejor la factorización de enteros?PP{\sf P}NPNP{\sf