Sea Q = (1,1,s) con s:
While X1 != 0 do
X1 := X1 + 1;
od Fq (n) = n+1 Fq(0) = ↑ Fq(1) = ↑.
¿Cuántas configuraciones iniciales distintas hay en una MT para una expresión de cinta dada? Una Un número finito, que puede ser mayor que uno Infinitas.
Sea Q=(1,1,s) con s:
While X1 != 0 do
X1 := X1 -1;
od Tq(n) = 3n + 1 Tq(n) = 4n + 1 Tq(n) = 4n + 2.
En una MT, para una expresión de cita dada: puede haber infinitas configuraciones terminales siempre hay infinitas configuraciones terminales siempre hay un número finito de configuraciones terminales.
En una MT: transitar en al menos un paso es el cierre transitivo de transitar en un paso transitar es el cierre transitivo de transitar en un paso transitar es el cierre transitivo de transitar en al menos un paso.
Si las funciones suma y resta son las habituales para naturales, entonces: μ[suma] = μ[π^2_1] suma = <π^2_1 | σ(π^2_2) μ[suma] = μ[resta].
Marca la afirmación correcta: Una función Turing-computable siempre es Turing-decidible Un conjunto Turing-decidible siemrpe es Turing-computable Un conjunto Turing-decidible siempre es Turing-enumerable.
Si Fq = σ entonces: Q = (0,1, X1:=0) Q = (1,1, X1 := X1+1) Q = (2,2, X1 := X2).
Si f = <π^1_1 | <θ|π^2_1> (π^3_3)> entonces f(3,1) 3 2 4.
Dos MT con distinto alfabetos: no pueden tener el mismo método de operación si tienen el mismo método de operación los alfabetos tienen el mismo cardinal puede tener el mismo método de operación con alfabetos de distinto cardinal.
Elige la opción correcta: Toda función computable es total Ninguna de las otras dos respuestas es verdadera Toda función total es computable.
Sea Q = (k, k, X1 := Xi) con k>= 1 y 1 <= i <=k: Fq = θ Fq = Π^k_i Fq = Π^i_k.
Si una MT tiene k estados y n símbolos en su alfabeto, entonces el número de filas de su tabla es: n*(k+1) k*(n+1) n*k.
Sea Q = (1,1,s) con s:
While X1 != 0 do
X1 := X1 + 1;
od Tq(0) = 2 Tq(0) = ↑ Tq(0) = 1.
¿Cuál de las siguientes expresiones es la definición de la función constante de dos argumentos que devuelve uno? σ( <θ|π^2_2>) σ(<<θ|π^2_2>| π^3_3>) σ( <<θ|π^1_1>|π^3_3>).
Dada una función recursiva cualquiera, se cumple que: La función es WHILE-computable La función es Turing-decidible Existe una MT que la representa y que para cualquier configuración inicial se detiene en un número finito de pasos.
Una función recursiva f definida mediante el operador de minimización no acotada (f = 𝝻[g]) puede ser una función total es una función parcial sólo si la función auxiliar g es también parcial es una función parcial en cualquier caso.
Elige la opción correcta: Toda función total es una función computable El cardinal del conjunto T-REC es el mismo que el cardinal del conjunto REC Toda función computable es una función total.
TREC es: Un subconjunto propio de las funciones recursivas: F(WHILE) El conjunto de todas las funciones recursivas.
Una función recursiva f calculada como composición de funciones recursivas, tiene un número de argumentos: igual al número de argumentos de la función externa de la composición igual al número de argumentos de las funciones internas de la composición igual al número de funciones internas de la composición .
Considera una MT que Turing-decide un conjunto A. La MT colocada detrás de una cadena cualquiera: siempre se para siempre se para sobre una celda vacía puede o no pararse.
Un predicado es recursivamente decidible sí y sólo si su función característica asociada es parcial si es el predicado asociado de alguna función recursiva total si es enumerable.
|
