CYC

Si ΛTd es el conjunto de lenguajes Turing-decidibles y Λ0 es el conjunto de lenguajes generados por gramáticas tipo 0 (cero) de Chomsky, lo correcto es: A. B. C.

La jerarquía de clases de complejidad en la notación "o mayúscula" es: O(logN) ⊂ O(NlogN) ⊂ O(N) ⊂ O(2^N) ⊂ O(N^2). O(logN) ⊂ O(N) ⊂ O(NlogN) ⊂ O(N^2) ⊂ O(2^N). O(N) ⊂ O(N^2) ⊂ O(logN) ⊂ O(NlogN) ⊂ O(2^N).

La máquina de Turing universal Muniv: No puede existir (problema de la parada). Para con algunas cadenas de entrada. Para con todas las cadenas de entrada.

Uno de los primeros problemas matemáticos de los cuales se supo que estaban en NP fue: Problema de la correspondencia de Post. Problema de la parada de la Máquina de Turing. Problema del viajante.

La N de NP es la inicial de: <<no polinómico>>. <<no decidible>>. <<no determinista>>.

En la siguiente máquina de Turing M: bababbbϵR(M). bababbbϵL(M). bababbbϵB(M).

La tesis de Church-Turing sostiene que: La máquina de Turing es el modelo de cálculo más general que existe. Los algoritmos con una tasa exponencial son eficientes. Las gramáticas de Chomsky son equivalentes a las máquinas de Turing.

El módulo DΔ (derecha hasta blanco): Sólo puede usarse para máquinas generadoras. Es imposible que produzca bucle sin fin. Es posible que produzca bucle sin fin.

El módulo Da aplicado a la configuración Δaba(a): ((a) significa que el puntero está ahí). Produce la configuración Δaba(a) (es decir, no hace realmente nada). Produce la configuración Δabaa(Δ). No acaba nunca.

El lenguaje {a^n b^n c^n | n > 0} es importante porque: No es independiente del contexto. Puede ser reconocido con un autómata con pila determinista, pero no con un autómata con pila no determinista. Puede ser expresado con una fórmula, pero no con una gramática de tipo 0 (cero).

Tengo un lenguaje lo meto en una MT y para en una a: L(M): Conjunto de cadenas que desembocan en el estado de parada (qh --> estado final), por lo tanto, lenguajes aceptados por M. B(M): Conjunto de cadenas en que la máquina no para nunca. R(M): Conjunto de cadenas que llevan a la máquina a situación de error, bien por rebasar el estado izquierdo o bien por estar en un estado del que no existe transición posible.

El problema del viajante (TSP, traveling salesman problem): Se puede resolver con un algoritmo determinista eficiente (por lo que está en P), pero los algoritmos no deterministas conocidos tienen tasa exponencial. No se sabe si está en la clase P o en la clase NP, ya que todavía no se sabe si P=NP. Se puede resolver con un algoritmo no determinista eficiente (por lo que está en NP), pero los algoritmos deterministas conocidos tienen tasa exponencial.

Los autómatas finitos no deterministas reconocen: Más lenguajes que los autómatas con pila deterministas. Menos lenguajes que los autómatas con pila deterministas. Los mismos lenguajes que los autómatas con pila deterministas.

Se ha demostrado que las gramáticas de Chomsky son equivalentes a las máquinas de Turing. Ello: Demuestra la tesis de Church-Turing. Pone en duda la tesis de Church-Turing. Apoya la tesis de Church-Turing.

El lenguaje L = {ω = ω^R | ω ∈ {a,b}*} ha de ser recordado porque: Puede ser reconocido con un autómata con pila no determinista, pero no con un autómata con pila determinista. Puede ser expresado con una fórmula, pero no con una gramática de tipo 2. Es dependiente del contexto pero no terminal.

El arte está en: Unas palabras en francés. Unas letras griegas. Unas palabras en inglés.

Un argumento a favor de la tesis de Church-Turing es que: Nadie ha encontrado un algoritmo eficiente para el problema del viajante. La máquina de Turing no determinista no se puede simular con una máquina de Turing determinista. Todos los lenguajes de programación de propósito general tienen similar capacidad de solución de problemas.

El problema P = NP significa: No se sabe si hay algún problema que esté en P y no en NP, ni lo contrario. Todo lo que se puede hacer con tasa polinómica con una máquina de Turing no determinista (NP) se puede hacer con una determinista (P). No se sabe si hay algún problema que esté en NP y no en P, ni lo contrario.

Si la máquina modular SD (suprimir derecha) se aplica a la cadena ΔaaaΔaa(a)aa, ¿Cuál es la configuración que resulta? ((a) significa que el puntero está ahí). ΔaaaΔa(a)aa. Δ(a)aaΔaaaa. ΔaaaΔaa(a)a.

Por definición, un lenguaje es Turing-decidible: Si tiene una máquina de Turing. Si tiene una máquina de Turing que para con todas las cadenas de entrada. Si tiene una máquina de Turing modular.

Se considera que no pueden ser eficientes los algoritmos: Logaritmicos. Exponenciales. Lineales.

Los autómatas finitos no deterministas reconocen: Más lenguajes que las expresiones regulares. Menos lenguajes que las expresiones regulares. Los mismos lenguajes que las expresiones regulares.

Los autómatas con pila deterministas reconocen: Menos lenguajes que los AFD. Más lenguajes que los AFD. Los mismos lenguajes que los autómatas finitos deterministas.

Los autómatas finitos no deterministas reconocen: Más lenguajes que los autómatas finitos deterministas. Menos lenguajes que los autómatas finitos deterministas. Los mismos lenguajes que los autómatas finitos deterministas.

Para demostrar que todo lenguaje aceptado por una máquina de Turing no determinista puede ser aceptado con una máquina de Turing determinista: Una máquina de una cinta en la que se van aplicando todos los caminos. Te sientas en la 305, blanco, entoces derecha, si el sujeto esta haciendo el examen de recuperacion derecha y si es blanco te sientas, si no esta haciendo el examen de recuperacion pasas a la siguiente fila y te preguntas como cojones ha hecho para hacer tan complicado algo tan simple. Una máquina de 3 cintas en la que se van aplicando todos los caminos.

El arte está en que: En una exposición de pintura: - ¿A usted le gusta la pintura? - Mucho, pero mas de un bote me empalaga. Una cosa no es lo que es, sino su representación.

El lenguaje {a^n b^n |n>0} es importante porque: Es independiente del contexto y regular. No es independiente del contexto. Es independiente del contexto pero no regular.

Dado el alfabeto T({a,b}*): La cadena vacía no pertenece a T. T* no es un lenguaje. T* no está vacío.

Se ha demostrado que las gramáticas de Chomsky son equivalentes a las máquinas de Turing. Ello: Pone en duda la tesis de Church-Turing. Desmiente la tesis de Church-Turing. Apoya la tesis de Church-Turing.

Al demostrar (segunda postcondición del teorema de Kleene) que para todo autómata finito puede encontrarse una expresión regular equivalente, se garantiza que: ∆ER=∆AF. ∆ER⊇∆AF. ∆ER⊆∆AF.

Al demostrar (primera postcondición del teorema de Kleene) que toda expresión regular puede transformarse en un autómata finito equivalente, se garantiza que: ∆ER⊇∆AF. ∆ER⊆∆AF. ∆ER=∆AF.

Una máquina de Turing universal es: Un dispositivo que manipula símbolos sobre una tira de cinta según sea conveniente. La maquina que de la película "Descifrando el enigma". Un mecanismo capaz de procesar cualquier algoritmo.

La gramática es de S -> AB AB -> D aB -> Ba A -> bA|b. Tipo 0. Tipo 2. Tipo 1.

La gramática es de S -> AB AB -> aBA aB -> Ba A -> bA|b. Tipo 0. Tipo 1. Tipo 2.