B4

La funcion CODI para la codificación de programas se define como: CODI(Q) = ∂1^3(n,p, Codi(s)). CODI(Q) = ∂1^3(n,n + max{n,k}, Codi(s)). CODI(Q) = ∂1^3(n,p - max{n,k}, Codi(s)).

Si a la definicion de la funcion "Castor afanoso (Σ)" le añadimos que Σ(0) = 0. Σ es una funcion total pero no recursiva. la funcion Σ no es ni total ni recursiva. entonces Σ ∈ T-REC.

El programa "Añadir(z, s)" que se ejecuta dentro del programa "Simular": añade a la variable z la secuencia de instrucciones codificadas por s. añade a la lista de sentencias a ejecutar s, las sentencias del cuerpo del bucle z. añade el codigo s a continuacion del codigo codificado por z.

El programa Universal U(z, x) calcula. la funcion universal U[REC] por lo que tendrá n + 2 variables de entrada, n, z y x. el valor de salida del programa (n, max{n, k}, DeCodi(z)) para el vector de entrada x. el problema de la parada para programas de longitud n con entrada x.

Sea REC^n el conjunto de funciones recursivas de N^n en N. La funcion universal U[REC^n] verifica. U[REC^n]: N^2 -> N. U[REC^n]: N^(n+1) -> N. U[REC^n]: N^n -> N.

La funcion god es: recursiva y parcial. biyectiva y recursiva. parcialmente computable.

La funcion degod es: recursiva y no total. recursiva y total. biyectiva y recursiva.

Sabemos que WHILE ⊆ WHILE_A y que. F(WHILE_A) ⊆ F(WHILE). F(WHILE) ⊆ F(WHILE_A). F(WHILE_A) = F(WHILE).

La funcion Castor afanoso: es una funcion Turing-computable. puede ser calculada numericamente para cualquier valor de n si utilizamos un ordenador potente y esperamos el tiempo suficiente. no es una funcion Turing-computable.

Marque la opcion falsa: El cardinal de T-REC es igual al cardinal de REC. Toda funcion total es computable. Todo conjunto decidible es enumerable.

Codi(X1 := 0; X1:= X1 - 1) =. 64. 34. 32.

Dado el codigo s: While X1 != 0 do X1 := 0 od. codi(s) = 4. codi(s) = 9. codi(s) = 20.

Elige. A. B. C.

El predicado H^1 es: decidible porque es el predicado asociado a una funcion total. enumerable porque es el predicado asociado a una funcion recursiva. no enumerable porque es el predicado asociado a una funcion no computable.

Del Teorema de Equivalencia se concluye que: PRED(T-WHILE) = {Pf | f ∈ WHILE}. F(WHILE) ⊆ INI. REC = F(WHILE).

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

Dada la funcion Castor Afanoso (Σ) se cumple que: si m > n => Σ(m) > Σ(n), con m, n ∈ N. ∃ Q ∈ P^K | f = Fq -> f(n) >= Σ (n+k) ∀ n ∈ N. Σ ∈ F(WHILE).

La funcion Castor afanoso esta definida como: A. B. C.

Elige. Q = (k, k+2, s). Q = (k + 1, k + 3, s). Q = (k, k + 1, s).

Una funcion f es WHILE-computable si y solo si. existe un programa WHILE Q | Tq es total. puede representarse con una MT. ∈ T-WHILE.

Si codi(s) = 50 entonces: Codi (s) = 50. Codi (s) = god(50) - 1. Codi (s) = 49.

Una funcion f es WHILE-computable si y solo si. puede representarse con una MT. existe un programa WHILE Q | Tq es total. ∈ T-WHILE.

Marque la opcion falsa: Todo conjunto decidible es enumerable. El cardinal de T-REC es igual al cardinal de REC. Toda funcion total es computable.

Elige. CALq(5,4) = (5,4,4). CALq(5,4) = (5,4,5). CALq(5,4) = (5, 3, 4).

Codi ( X1 := 0; X1 := X1 - 1). 32. 64. 34.

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

Una funcion f es WHILE-computable si y solo si. Existe un programa WHILE Q | Fq = f. puede representarse como la composicion de funciones iniciales. existe un programa WHILE Q | Tq es total.

La funcion complejidad Temporal (T). No puede calcularse cuando no es posible alcanzar una configuracion terminal. es una funcion total para una entrada dada nos da el valor de.. La variable X1 al final del proceso de computo, siempre que se alcance una configuracion terminal.

Dado un código While s, se cumple que: la funcion salto(s, n) puede devolver un valor menor que n. la funcion salto(s, n) siempre devuelve un valor mayor que n. la funcion salto(s, n) es una funcion parcial.

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

La funcion reemplazar del programa universal (reem) es: una funcion parcial de 3 argumentos. una funcion total. una funcion inyectiva.

Elija la opcion correcta. A. B. C.

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

La funcion Castor afanoso es. una aplicacion biyectiva entre naturales. creciente (m > n entonces Σ(m) > Σ(n) ). parcialmente resoluble.

Si un problema es no resoluble entonces. No puede ser parcialmente resoluble. El predicado del que es asociado puede ser enumerable. el predicado del que es asociado no puede ser enumerable.

La longitud de un programa WHILE. a veces coincide con su tamaño y otras veces no. siempre es mayor que su tamaño. siempre es menor que su tamaño.

La funcion tipo es. inyectiva pero no sobreyectiva. sobreyectiva pero no inyectiva. biyectiva.

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

Marca la opcion verdadera: PRED(MT) I F(WHILE). F(WHILE) incluido en REC. DEC(MT) = REC.

El programa Reducir tiene. 1 entrada. 2 entradas. 3 entradas.

Marca la opcion verdadera: Σ(2) = 2. Σ(2) = 3. Σ(2) = 5.

Marca la opcion verdadera. INI ⊆ F(WHILE). INI pertenece a F(WHILE). INI = F(WHILE).

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

Toda indexacion de funciones es. sobreyectiva. biyectiva. invertible.

Elije la opcion correcta: Todo conjunto perteneciente al conjunto potencia de los natuales es un conjunto enumerable. Un conjunto perteneciente al conjunto potencia de los naturales puede no ser enumerable ni decidible. Todo conjunto perteneciente al conjunto potencia de los natuales es un conjunto decidible.