Talf Bloque 4

La función CODI para la codificación de programas se define como: CODI(Q) = σ³₁ (n, p, Codi(s)). CODI(Q) = σ³₁ (n, n + max{n, k}, Codi(s)). CODI(Q) = σ³₁ (n, p - max{n, k}, Codi(s)).

Si a la definición de la función "Castor afanoso (Σ)" le añadimos que Σ(0) = 0 : Σ es una función total pero no recursiva. la función Σ 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 código s a continuación del código codificado por z.

El programa Universal U(z, x̲) calcula: la función 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ⁿ el conjunto de funciones recursivas de Nⁿ en N. La función universal U[RECⁿ] verifica: U[RECⁿ] : N² -> N. U[RECⁿ] : Nⁿ⁺¹ -> N. U[RECⁿ] : Nⁿ -> N.

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

La función 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 función Castor afanoso: es una función Turing-computable. puede ser calculada numéricamente para cualquier valor de n si utilizamos u ordenador potente y esperamos el tiempo suficiente. no es una función Turing-computable.

Marque la opción falsa: El cardinal de T-REC es igual al cardinal de REC. Todo conjunto decidible es enumerable. Toda función total es computable.

Codi(X₁ := 0; X₁ := X₁ -1)=. 64. 35. 32.

Dado el código s: While X₁ ≠ 0 do X₁ := 0 od. codi(s) = 4. codi(s) = 9. codi(s) = 20.

El siguiente macroprograma Q = (k, k+1, s) con s: Se utiliza para demostrar: f = g(h₁, ..., hₘ) ∧ g, h₁, ..., hₘ ∈ F(WHILE) ⇒ f ∈ F(WHILE). f = <g|h> ∧ g ,h ∈ F(WHILE) ⇒ f ∈ F(WHILE). f = μ[g] ∧ g ∈ F(WHILE) ⇒ f ∈ F(WHILE).

El predicado H¹ es: decidible porque es el predicado asociado a una función total. enumerable porque es el predicado asociado a una función recursiva. no enumerable porque es el predicado asociado a una función 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 número de lenguajes no representables. igual que REC-TREC.

Dada la función Castor Afanoso (Σ), se cumple que: si m > n ⇒ Σ(m) > Σ(n), con m, n ∈ N. ∃ Q ∈ Pᵏ | f = FQ ⇒ f(n) ≥ Σ(n + k) ∀ n ∈N. Σ ∈ F(WHILE).

La función Castor afanoso está definida como: Primera definición. Segunda definición. Tercera definición.

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

Una función f es WHILE-computable si y sólo 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 función f es WHILE-computable si y sólo si. puede representarse con una MT. existe un programa WHILE Q | Tq es total. ∈ T-WHILE.

Elija la opción correcta. Primera. Segunda. Tercera.

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

Una función f es WHILE-computable si y sólo si. existe un programa WHILE Q | Fq = f. puede representarse como la composición de funciones iniciales. existe un programa WHILE Q | Tq es total.

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

El problema de la parada para programas con una entrada (dado por el predicado H¹). es parcialmente resoluble. ∈ TREC. es no numerable.

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

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

Elija la opción correcta: U[REC¹] es una función total. U[RECⁿ] ∈ U[RECⁿ⁺¹]. U[RECⁿ] ∈ U[RECⁿ].