Test bloque 2 talf

{(x,y)∈ℕ^2 : x = y }. es el conjunto de valores de verdad del predicado x != y. es un conjunto recursivamente decidible. no es generable.

consideremos la funcion recursiva f = μ[g]. Entonces: g tiene al menos un argumento. f tiene al menos un argumento. si f no es una funcion total, g tampoco lo es.

¿Cual de las siguientes expresiones NO es una funcion recursiva?. μ[θ]. <θ | π_{2}^{2}>. σ(θ).

¿Cual de estas funciones recursivas es la función constante f(x) = 0?. σ(θ). <π_{1}^{1} | π_{3}^{1}>. <θ | π_{2}^{2}>.

Representando el numero n con n+1 trazos y colocando esta MT detras de una cadena que representa un numero natural mayor que cer. ¿Que funcion representa esta MT? q0 * | q0 q0 | r q1 q1 * h q1 q1 | | q1 (Por ejemplo, la máquina prodría iniciar el cómputo en *|||*). f(x) = x-1, x∈ℕ. f(x) = x+1, x∈ℕ. f(x) = x-2, x∈ℕ.

Consideremos un conjunto A∈DEC(MT), y sea M una MT que turing-decide dicho conjunto. Si colocamos M detras de unas cadenas cualesquiera, entonces. parara solamente en un simbolo del alfabeto. se para sobre un cuadrado de la expresion de cinta. pordria parar o no parar, segun las cadenas de la expresion de cinta.

Una MT realiza la transicion (q2, ... *101* ..., 7)⊢(q5, ...*101* ..., 8), porque su tabla contiene la linea. (q5 1 r q2). (q2 1 l q5). (q2 0 r q5).

Consideremos la funcion recursiva f = μ[<π_{1}^{1} | σ(π_{3}^{3}) >], ¿Qué podemos decir sobre su predicado asociado P_f?. P_f es un preficado recursivamente decidible. ¬(P_f(x), ∀x != 0 (el simbolo ¬ indica que es falso). El conjunto de valores de verdad es V_{P_{f}} != ∅.

Una funcion While-calculable es aquella que se puede representar mediante. al menos, un programa en while. un programa que solo contiene instrucciones de asignacion. un programa que contiene uno o mas bucles indefinidos.

Si un predicado es turing-decidible, entonces. existe una funcion turing-calculable total que es la funcion asociada a dicho predicado. no siempre sabremos si un vector de argumentos lo hace cierto. se puede enumerar su conjunto de verdad, pero no el complementario de este.

<θ | π_{1}^{2}> (4) =. 2. 3. 8.

¿Cual de estas MT realiza el calculo ...*1w*... =>...*1w*..., si w ∈{1}*?. (q0 * h q0), (q0 1 r q0). (q0 * r q0), (q0 1 h q0). (q0 * * q0), (q0 1 r q0).

El programa While(2, while X2 != 0 do X1:= X1+1; X2:=X2-1 od) verifica. (1, 3, 2)⊢(5, 3, 2). (4, 3, 2)⊢(1, 3, 2). (1, 3, 2)⊢(2, 4, 2).

¿Cual de estos vectores es configuracion valida del programa WHILE(2, X1:=0; X1:=X1)?. (0, 3). (3, 0). (2, 0, 7).

Si una maquina de turing verifica γ(q,s)∈{r, l}, ∀s∈Σs, ∀q∈K, entonces la funcion que representa. no esta definida para ningun valor del dominio. esta definida para un conjunto finito de valores del dominio. es total.

CAL_{1,X2:=X1;while X2!=0 do X2:=X2-1 od; X1:=X2) (3, 4) es igual a. (2, 3, 2). (3, 2, 3). (2, 3, 3).

Dado el programa While Q = (0, while X1 != 0 do X1:= X1+1 od). F_Q() = \uparrow. F_Q() = 0. F_Q() = 1.

¿Cual de las siguientes afirmaciones es cierta?. Si un conjunto es WHILE-enumerable entonces debe ser WHILE-decidible. Toda funcion WHILE-computable es total. Si f ∈T-WHILE => P_f ∈PREF(WHILE).

TREC es un conjunto de funciones. igual al conjunto de funciones recursivas. que incluye a las funciones iniciales. subconjunto de INI.

La complejidad temporal T_(1, X2:=X1; while X2!=0 do X2:=X2-1 od;X1:=X2) (3) es igual a. 12. 15. 17.

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

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

<π_{1}^{2} | π_{1}^{4}>=. 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 F_Q = σ(σ(π_{2}^{4})). 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 verifica que. Σ∈REC. habria valores para los que Σ divergiria. Σ∈TREC.

Si Q = (5, s) entonces U[REC⁵](while2N(Q), 2, 0, 1, 1, 4) =. F_Q (0, 1, 1, 4). ↑ (diverger). F(5, s)(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 simbolo no vacios.

La codificacion de Cantro de ℕ³ establece. una biyeccion entre ℕ y ℕ³. una biyeccion entre ℕ³ y ℕ*. una sobreyeccion con los programa While de 3 argumentos.

Referida a la codificación de Godel, ¿Cuál de estas afirmaciones es cierta?. ∃p, q, r∈ℕ : p != q∧γ(p, r) = γ(q, r). ∃p, q∈ℕ, x∈ ℕ^p, y ∈ ℕ^q : p != q ∧Γ(x) = Γ(y). ∃k ∈ℕ, x, y ∈ℕ^k : x != y ∧Γ(x) = Γ(y).

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

si g∈REC: ℕ⁴ -> ℕ∧ f = μ[g] ∧F_Q = f entonces, basandonos en la demostracion del teorema de equivalencia: F_Q ∈F(WHILE)³. F_Q ∈F(WHILE)⁴. F_Q ∈F(WHILE)².

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

Según el teorema de equivalencia: REC es subconjunto propio de F(WHILE). f∈REC => ∃Q∈ WHILE: F_Q = 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² + y² + 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.

¿Cual de estas propiedades es cierta?. ℕ² ∈ ℕ*. () !∈ ℕ*. ℕ ⊂ ℕ*.

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.

∀z∈ℕ, z = (σ_{1}^{2}(σ_{2,1}^{1}(z), σ_{2,2}^{1}(z)). es una proposición cierta. es falso para un número finito de valores de z. solo en el caso de que z = σ_{1}^{2}(z, z).