miemboviril

Del teorema de equivalencia podemos deducir que: REC = F(T-WHILE). existe un programa universal. REC (pertenece) F(WHILE).

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.

Marca la afirmación correcta: Una función Turing-Computable siempre es Turing-Decidible. Un conjunto Turing-Decidible siempre es Turing-Computable. Un conjunto Turing-Decidible siempre es Turing-Enumerable.

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.

Para la MT dada por la tabla 0 * L 1 0 | L 1 1 * h 1 1 | L 1. existe sólo una configuración inicial para la cual la MT no se para. no existe ninguna configuración inicial para la cual la MT no se para. existe más de una configuración inicial para las cuales la MT no se para.

Sea M = {K, q0, ∑, δ, γ) una MT con K = {q0, q1, q2, q3} , ∑ = {0,1} y funciones de transición e instrucción dadas por la siguiente tabla: q0, * -> q0, r q0, 0 -> q1, r q0, 1 -> q2, r q1, * -> q3, 0 q1, 0 -> q1, r q1, 1 -> q2, r q2, * -> q3, 1 q2, 0 -> q2, r q2, 1 -> q1, r q3, * -> q3, h q3, 0 -> q3, r q3, 1 -> q3, r Dada la configuración inicial (q0, ... *_* 1101**...) (está subrayado el elemento de la izquierda a _ ). (q3, ... **110*_**...). (q3, ...**11011_*...). (q3, ...**11011*_...).

Una función recursiva: puede ser parcial si para su definición se utiliza el operador de minimización no acotada. es parcial si para su definición se utiliza el operador de minimización no acotada. no puede ser parcial.

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.

Sea una función recursiva f = σ(μ[g]), con g = <∏11| σ (∏ 33) > Entonces: f(1) = 0. f(1) = ↑. f(0) = 0.

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.

Indicar el valor de la función siguiente para n=3, m=1: f(n,m)=⟨π11|predecesor3⟩(n,m), donde la función predecesor3 está definida como: predecesor3(n1,n2,n3) = n3−1. f(3,1)=0. f(3,1)=2. f(3,1)=4.

Indicar el valor que se obtiene al evaluar la siguiente función recursiva para n=2. f(n)=μ[resta(π21,producto(π22,π22))](n) donde resta es la función recursiva "resta natural" y producto la operación "producto" entre dos naturales. f(2)=1. f(2)=2. f(2)=0.

Indicar el valor de la función f(n,m)=suma(resta(π21,π22),resta(π22,π21))(n,m) para n=4 m=2, donde suma es la función "suma" entre dos naturales y resta es la función "resta natural" entre dos naturales es: f(4,2)=6. f(4,2)=2. f(4,2)=1.

Una tabla de una MT. no puede tener sólo una fila. no puede tener sólo dos filas. siempre tiene un número par de filas.

Sea M la MT especificada por la tabla indicada abajo, marque la configuración terminal que se obtiene para la configuración inicial (0, ...* || * || * ... ). 0 * L 1 0 | L 1 1 * | 2 1 | L 1 2 * L 3 2 | R 2 3 * L 4 3 | * 3 4 * h 4 4 | * 4. (4, ... * ||| * ... ). (0, ... * ||| * ... ). (4, ... * |||| * ... ).

La función recursiva 〈θ | π21 〉 es la función. constante cero de un argumento. máximo {n-1, 0}. constante cero de dos argumentos.

El conjunto de configuraciones de una MT. puede ser finito o infinito dependiendo de la MT. siempre es infinito. siempre es finito.

La expresión de cinta de una MT es una aplicación que. nunca es biyectiva. a veces puede ser biyectiva y otras veces no. siempre es biyectiva.

La tercera columna de una tabla de una MT representa. la función de parada. la función de transición. la función de instrucción.

Una Máquina de Turing de un estado sobre una cinta no vacía. puede parar sobre el cuadrado escrutado inicial. nunca se para. para con cualquier contenido de la cinta.

En una tabla de una MT. si en la tercera columna no hay elementos repetidos entonces tiene menos de tres estados. en la tercera columna siempre hay elementos repetidos. si en la tercera columna hay elementos repetidos entonces tiene más de dos estados.

El concepto de sistema de numeración es: posterior a la aparición del número cero. anterior a la aparición del número cero. simultáneo con la aparición del número cero.

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.

En una recursión primitiva. la función base tiene un argumento menos que la función de inducción. la función base tiene dos argumentos menos que la función de inducción. la función base tiene los mismos argumentos que la función de inducción.

Si un programa WHILE de tamaño 6 transita directamente de (5, 1, 1) a (2,1,1), entonces su código. contiene bucles. no contiene asignaciones a cero. contiene seis asignaciones.

Sea Q = (1, 2, s) un programa WHILE cuyo código se describe a continuación: s: X2 := X1 – 1 ; while X1 ≠ 0 do X1 := X1 – 1 ; X1 := X1 – 1 ; X2 := X2 + 1 ; X2 := X2 + 1 ; od ; X1 := X2. CALQ(5,5) = (6,4,5). CALQ(5,5) = (5,4,4). CALQ(5,5) = (6,3,5).

La longitud de un programa WHILE. puede coincidir con su tamaño. siempre es menor que su tamaño. siempre es mayor que su tamaño.

Una función f es WHILE-computable si y sólo si. existe un programa WHILE Q | TQ es total. ∈ T-WHILE. puede representarse con una MT.

F(WHILE) es un conjunto con cardinal. igual al número de lenguajes no representables. infinito no numerable. igual que REC-TREC.

Sea Q=(1,2,s) con s: X2:=X1; While X2≠ 0 do X1 := X1 + 1 ; X2 := X2 - 1 ; od X1 := X1 + 1. TQ(n)=3n+3 ∀ n ∈ N. TQ(n)=4n+2 ∀ n ∈ N. TQ(n)=4n+3 ∀ n ∈ N.

Elija la opción correcta: U[RECn]∈RECn+1. U[REC1] es una función total. U[RECn]∈RECn.

Sea el programa WHILE Q = (1, 1, X1:=X1+1;X1:=X1+1). TQ(3) = 2. CALQ(3,2) = (4,5). FQ = σ (con σ ∈ INI).

Sea Q = (1, 2, s) un programa WHILE cuyo código se describe a continuación: s: X2 := X1 – 1 ; while X1 ≠ 0 do X1 := X1 – 1 ; X1 := X1 – 1 ; X1 := X1 – 1 ; X2 := X2 + 1 ; X2 := X2 + 1 ; X2 := X2 + 1 od ; X1 := X2. CALQ(5,4) = (5,4,5). CALQ(5,4) = (5,4,4). CALQ(5,4) = (5,3,4).

En el modelo de funciones recursivas, el símbolo pi (Π) representa: Un subconjunto de TREC. Una función inicial. Un conjunto finito de funciones.

σ(θ) es: Una función recursiva parcial. Una recursión primitiva de funciones iniciales. Una función constante.

Una Máquina de Turing de un estado sobre una cinta no vacía. No puede parar a más de dos posiciones del cuadrado escrutado inicial. Puede parar sobre el cuadrado escrutado inicial. Para con cualquier contenido de la cinta.

F(WHILE) es un conjunto con cardinal. Igual al número de lenguajes no representables. Igual que REC-TREC. Infinito no numerable.

El número de filas de la tabla de una MT con n estados y sobre un alfabeto de a símbolos es: (a+1)*n. a*n. a*n+1.

La función complejidad Temporal (T). es una función total. no puede calcularse cuando no es posible alcanzar una configuración terminal. para una entrada dada nos da el valor de la variable X1 al final del proceso de cómputo, siempre que se alcance una configuración terminal.

El predicado tiene: n argumentos. n+1 argumentos. dos argumentos.

Sea Q=(k, k, X := X ). Entonces es la función: Π(k+i) i. Πk i. Πi k.

σ ∈ F(WHILE) porque. dado Q=(1, 1, X :=X +1), Fq ∈ WHILE. dado Q=(1, 1, X :=X +1), Fq = σ.

El predicado H^1 es parcialmente resoluble. porque es el predicado asociado a la función computable f = σ(U[REC^1]). porque no es resoluble. porque es el predicado asociado a la función Σ.

Sea Q=(1,2,while X ≠0 do X :=X -1 od). F(3) es igual a: 3. ↑. 0.

Si H (g,x_ ) ^n es falso, entonces. el programa g con la entrada x_ ∈ ℕ^n no termina. el programa x_∈ ℕ^n con la entrada g no termina. el programa x_ con la entrada g termina tras un número finito de pasos.

U[REC^(n+1) ] ∈. REC^(n+1). REC^(n+2). REC^n.

Si g: N^k -> N Λ h: N^(k+2) -> N Λ f = <g|h> Λ Fq = f entonces: Q = (k, k+2, s). Q = (k+1, k+3,s). Q = (k, k+1, s).

Marca la opción verdadera: f = μ[g] ⇒ f ε F(WHILE). f = g(h) Λ g, h ε TREC ⇒ f ε T-WHILE. f= g(h) Λ f !ε REC ⇒ g !ε F(WHILE).

Si σ 2 1(3,4)=32 entonces. codi( X3 := X4 – 1 ) = 162 . codi( X4 := X5 – 1 ) = 163 . codi( X4 := X5 – 1 ) = 162 .