BLOQUE 4 TALF

Dado Q=() ¿Fq ∈ REC?. no, ya que σ(σ(θ)). si. no, Fq ∈ F(WHILE) , pero FQ ∉ REC.

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

Dado: F(3,X1=X2+1). F(3,X1=X1). F(2,X1=X2).

s = X5001 = X129. s = while X1 ≠ 0 do; od. s= X3=X2; X1=X2;.

Determina que Q ∈ WHILE verifica FQ = σ(σ(pi(4,2)). Q= (4,4,X1=X2; X1=X1+1;X1=X1+1). Q= (4,4,X2=X4; X2=X1+1;X1=X2+1). Q= (4,4,X4=X2; X4=X1+1;X4=X1+1).

Si el problema de la parada fuera resoluble, entonces se verificaria que. Σ ∉. REC. Σ ∈ TREC. habria valores para los que Σ divergiria.

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

La maquina de Turing universal tiene como entrada. al menos tantos simbolos no vacios como estados tenga la maquina universal. una maquina de Turing y sus argumentos. infinitos simbolos no vacios.

La codificacion de Cantor de N^3 establece. una biyeccion entre N y N^3. una biyeccion entre N^3 y N*. una sobreyección con los programas While de 3 argumentos.

X. Y.

X. Y.

La funcion Castor afanoso verifica. Σ(1201)<Σ(1202). Σ(1201)=Σ(1202). Σ(1201)>Σ(1202).

FQ ∈ F(WHILE)^3. FQ ∈ F(WHILE)^4. FQ ∈ F(WHILE)^2.

El predicado H^1 es. decidible. no generable. recursivamente enumerable.

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

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

¿Cual 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 funcion recursiva total que lo define. es parcialmente resoluble.

es una proposicion cierta. es falso para un numero finito de valores z.

Si 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 a 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 tendra 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 de Castor Afanoso. es una funcion Turing computable. no es una funcion Turing computable. puede ser calculada numericamente para cualquier valor de n si utilizamos un ordenador potente y esperamos el tiempo suficiente.

Marque la opción falsa. El cardinal de TREC 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 predicado H1 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. REC = F(WHILE). F(WHILE) ⊆ INI. PRED(T-WHILE) = {Pf | 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. Σ ∈ F(WHILE).