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ⁿ].
|
