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