talf bloque 4

Dado Q = (0,X1:=X1+1;X1:=X1+1=¿Fq € REC?. no, ya que σ(σ(θ)) !∈ REC. sí. no, Fq € F(WHILE), pero Fq !∈REC.

El natural 55 codifica la sentencia. while X11 != 0 do X1:=0 od. X12 := 0. X11 := X12.

< π(2,1) | π(4,1) > =. F(3,X1:=X2+1). F(3,X1:=X1). F(2,X1:=X2).

Q = (2,s) ∈ while ^ |s|do + |s|:= = 1 si. s = X5001 := X129. s = WHILE X1 != 0 do;od. s = X3 := X2; X1 := X2.

Determina que Q ∈ WHILE verifica Fq = σ(σ(π(4,2)). Q = (4,x2:=x4;x2:=x1+1;x1:=x2+1). Q = (4,x1:x2;x1:=x1+1;x1:=x1+1). Q = (4,x4:=x2;x4:=x1+1;x4:=x1+1).

Si el problema de la parada fuera resoluble, entonces se verificaría que. Σ !∈ REC. habría valores para los que Σ divergiría. Σ ∈ TREC.

Si Q = (5,s) entoences U[REC^5](while2N(Q),2,0,1,1,4) =. F(5,s) (2,0,1,1,4). Fq(0,1,1,4). ↑.

La máquina de Turing universal tiene como entrada. al menos, tantos símbolos no vacíos como estados tenga la máquina universal. una máquina de turing y sus argumentos. infinitos símbolos no vacíos.

La codificicación de cantor de N^3 establece. una biyección entre N y N^3. una biyección entre N^3 y N*. una sobreyección con los programas WHILE de 3 argumentos.

Referida a la codificación de Gödel, ¿Cuál de estas afirmaciones es cierta?. ∃p,q,r ∈ N : p ≠ q Λ δ(p,r) = δ(q,r). ∃p,q,r ∈ N,x ∈ N^p, y ∈ N^p : p ≠ q Λ Γ(x) = Γ(y). ∃k ∈ N, x,y ∈ N^k : x ≠ y Λ Γ(x) = Γ(y).

Referida a las codificaciones de Cantor, ¿Cuál de estas afirmaciones es FALSA?. ∃ p,q ∈ N,x ∈ N^p, y ∈ N^q : p ≠ q Λ σ(p,1) (x) = σ(q,1) (y). ∃ p,q ∈ N,x ∈ N^p, y ∈ N^q : p ≠ q Λ σ(p,1) (x) = σ(q,p) (y). ∃ p,q,r ∈ N,x ∈ N^p, y ∈ N^q : p ≠ q Λ σ(1,q,r) (x) = σ(1,p,y) (y).

La función Castor afanoso verifica. Σ(1201) < Σ(1202). Σ(1201) = Σ(1202). Σ(1201) > Σ(1202).

Si g ∈ REC: N^4 → N Λ f = μ[g] Λ Fq = f entonces, basándonos en la demostración del teorema de equivalencia: Fq ∈ F(WHILE)^3. Fq ∈ F(WHILE)^4. Fq ∈ F(WHILE)^2.

El predicado H^1 (asociado al problema H^1) es. decidible. no generable. recursivamente enumerable.

Según el Teorema de equivalencia: REC es subconjunto propio de F(WHILE). f ∈ rec => ∃Q ∈ WHILE : Fq = f. T - WHILE es un conjunto de funciones no computables.

Siendo P y S dos programas WHILE para el producto y suma de dos naturales, respectivamente, ¿Cuál de estos programas demuestra que f(x,y) = x^2+y^2+2xy es una función recursiva?. (2,X3:=S(X1,X2=;X4:=S(X1,X2);X5:=P(X1,X2);X6:=P(X3,X4);X1:=S(X5,X6)). (2,X3 := S(X1,X2);X4:=S(X1,X2);X1:=P(X3,X4)). (2,X3:=P(X1,X2);X4:=P(X1,X2);X1:=S(X3,X4)).

Σ(6)=. Σ(5). 2·Σ(3). 7.

¿Cuál de estas proposiciones es cierta?. N^2 ∈ N*. () !∈ N*. N ⊂ N*.

Un problema es no resoluble si. no se puede definir en base a un predicado decidible. existe una función recursiva total que lo define. es parcialmente resoluble.

∀z ∈ N, z = σ(2,1) (σ(1,2)(z),σ(1,(2,2))(z)). es una proposición cierta. es falso para un número finito de valores de z. sólo en el caso de que z = σ(2,1)(z,z).

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 tendar 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.

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. Todo conjunto decidible es enumerable. Toda funcion total es computable.

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

El siguiente macroprograma Q=(k,k+1,s) con s: while g(X1,X2,...,Xk,Xk+1) od; X1:=Xk+1 se utiliza para demostrar que: f = g(h1,...,hm) ∧ g,h1,...,hm ∈ F(WHILE) ⇒ f ∈ F(WHILE). f = <g|h> ∈ F(WHILE) ⇒ f ∈ F(WHILE). f = μ[g] ∧ g ∈ F(WHILE) ⇒ f ∈ F(WHILE).

De la función 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).