TALF

Sea Q = (1, 2, s) un programa WHILE cuyo código se describe a continuación: s: X2 := X1 – 1 ; while X1 ! 0 do X1 := X1 – 1 ; X1 := X1 – 1 ; X1 := X1 – 1 ; X2 := X2 + 1 ; X2 := X2 + 1 ; X2 := X2 + 1 od ; X1 := X2. CALQ(5,4) = (5,3,4). CALQ(5,4) = (5,4,5). CALQ(5,4) = (5,4,4).

Elija la opción correcta: U[RECn] ! RECn. U[REC1] es una función total. U[RECn] ! RECn+1.

Marque la opción falsa: Todo predicado enumerable es decidible. Toda función total es computable. El cardinal de T-REC es igual al cardinal de REC.

El predicado H1 es parcialmente resoluble. porque no es resoluble. porque es el predicado asociado a la función computable f = !(U[REC1]). porque es el predicado asociado a la función ".

La función complejidad Temporal (T). es una función total. no puede calcularse cuando no es posible alcanzar una configuración terminal. para una entrada dada nos da el valor de la variable X1 al final del proceso de cómputo, siempre que se alcance una configuración terminal.

Si a la definición de la función "Castor afanoso (")" le añadimos que "(0)=0 entonces. es una función total pero no recursiva. ! T-REC. la función " no es ni total ni recursiva.

Si un programa WHILE de tamaño 6 transita directamente de (5, 1, 1) a (2, 1,1), entonces su código. contiene bucles. contiene seis asignaciones. no contiene asignaciones a cero.

La función complejidad Temporal (T). para una entrada dada nos da el valor de la variable X1 al final del proceso de cómputo, siempre que se alcance una configuración terminal. no puede calcularse cuando no es posible alcanzar una configuración terminal. es una función total.

Del Teorema de Equivalencia podemos concluir que: existe un programa universal. REC = F(T-WHILE). REC ⊆ F(WHILE).

Una función f es WHILE-computable si y sólo si. existe un programa WHILE Q | TQ es total. ! T-WHILE. puede representarse con una MT.

Toda indexación de funciones es. biyectiva. invertible. sobreyectiva.

Dado un código While s, se cumple que: la función salto(s , n) siempre devuelve un valor mayor que n. la función salto(s, n) es una función parcial. la función salto(s , n) puede devolver un valor menor que n.

Elija la opción correcta: Todo conjunto perteneciente al conjunto potencia de los naturales es un conjunto enumerable. Todo conjunto perteneciente al conjunto potencia de los naturales es un conjunto decidible. Un conjunto perteneciente al conjunto potencia de los naturales puede no ser enumerable ni decidible.

F(WHILE) es un conjunto con cardinal. infinito no numerable. igual que REC-TREC. igual al número de lenguajes no representables.

El problema de la parada para programas con una entrada (dado por el predicado H1). es parcialmente resoluble. es no enumerable. ! TREC.

Codi(X1 := 0 ; X1 := X1 – 1). 64. 34. 32.

Sea Q=(1,2,s) con s: X2:=X1 While X2! 0 do X1 := X1 + 1 ; X2 := X2 - 1 ; od. TQ(n) = 2n + 2 # n ! N. TQ(n) = 4n + 2 # n ! N. TQ(n) = 3n + 3 # n ! N.

La función Castor Afanoso es. una aplicación biyectiva entre naturales. parcialmente resoluble. creciente ( m > n ⇒ Σ(m) > Σ(n) ).

Sean Q y R dos programas WHILE distintos de 1 argumento, entonces. FQ(x) ! FR (y), $ x,y ! %. (FQ(x), FR (y)) ! %2, $ x,y ! %. CODI(Q) ! CODI(R).

La función reemplazar del programa universal (reem) es: una función total. una función inyectiva. una función parcial de 3 argumentos.

La función Castor Afanoso es. una aplicación biyectiva entre naturales. parcialmente resoluble. creciente ( m > n ⇒ Σ(m) > Σ(n) ).

F(WHILE) es un conjunto con cardinal. igual al número de languajes no representables. infinito no numerable. igual que REC-TREC.

Si M es un AFDM entonces. todos los AFD equivalentes tienen menos estados finales que M. existe un AFD equivalente con menos estados que M. todos los AFD equivalentes tienen mayor o igual número de estados que M.

Del Teorema de Equivalencia podemos concluir que: existe un programa universal. REC = F(T-WHILE). REC ⊆ F(WHILE).

El problema de la parada para programas con una entrada (dado por el predicado H^1). es parcialmente resoluble. ∈ TREC. es no enumerable.

La función reemplazar del programa universal (reem) es: una función parcial de 3 argumentos. una función total. una función inyectiva.

Una Máquina de Turing de un estado sobre una cinta no vacía. no puede parar a más de dos posiciones del cuadrado escrutado inicial. puede parar sobre el cuadrado escrutado inicial. para con cualquier contenido de la cinta.

El AFD M=(K, , ,s, F) con K={ , } y ={0,1}, con la función de transición especificada por: δ(q_0 , 0) = q 1 , δ(q_0 , 1) = q 0 , δ(q_1 , 0) = q 1 , δ(q_1 , 1) = q_0 , y con s= q_0 F_1= representa: un lenguaje con infinitas cadenas cuyo último símbolo es 0. un lenguaje con infinitas cadenas que no contienen 0. el conjunto vacío.

La función complejidad Temporal (T). no puede calcularse cuando no es posible alcanzar una configuración terminal. para una entrada dada nos da el valor de la variable X_1 al final del proceso de cómputo, siempre que se alcance una configuración terminal. es una función total.

σ(θ) es: una recursión primitiva de funciones iniciales. una función recursiva parcial. una función constante.

símbolo Pi ( π) representa: un conjunto finito de funciones. un subconjunto de TREC. una función inicial.

Marca la opción verdadera: INI ⊆ F(WHILE). INI ∈ F(WHILE). INI = F(WHILE).

Marca la opción verdadera: Σ(2) = 2. Σ(2) = 3. Σ(2) = ­­ ↑.

Marca la opción verdadera: f = 〈g|h〉 ⇒ f ∈ T-WHILE. f = 〈g|h〉 ^ g ∈ TREC ⇒ f ∈ TREC. f = 〈g|h〉 ^ f ∉ TREC ⇒ ( g ∉ TREC ^ h ∉ TREC ).

La función reem tiene. un argumento. dos argumentos. tres argumentos.

La longitud de un programa WHILE. siempre es menor que su tamaño. a veces coincide con su tamaño y otras veces no. siempre es mayor que su tamaño.

Si codi(s) = 50 entonces. Codi( s ) = 49 . Codi( s ) = 50 . Codi( s ) = god(50) - 1 .

La función tipo es. sobreyectiva pero no inyectiva. inyectiva pero no sobreyectiva. biyectiva.

Marca la opción verdadera: F(n, p, s) = F(n+i, p, s). F(n, p, s) = F(n+i, p+i, s). F(n, p, s) = F(n, p+i, s).

Marca la opción verdadera: f = μ[g] ⇒ f ∈ F(WHILE). f = g(h) ^ g, h ∈ TREC ⇒ f ∈ T-WHILE. f = g(h) ^∉ f Ï REC ⇒ g ∉ F(WHILE).

Si σ^2_1 (3,4)=32 entonces. codi( X3 := X4 – 1 ) = 162 . codi( X4 := X5 – 1 ) = 163 . codi( X4 := X5 – 1 ) = 162 .

Marca la opción verdadera: μ[ U[REC^1] ] ∈ TREC. μ[ U[REC^100] ] ∈ REC 100. μ[ U[REC^100] ] ∈ REC 101.

Marca la opción verdadera: DEC(MT) = REC. F(WHILE) ⊆ REC. PRED(MT) ⊆ F(WHILE).

El programa Reducir tiene. una entrada. dos entradas. tres entradas.

La función degod es. sobreyectiva pero no inyectiva. biyectiva pero no recursiva. biyectiva y recursiva.

Si un problema es no resoluble entonces. el predicado del que es asociado puede ser enumerable. el predicado del que es asociado no puede ser enumerable. no puede ser parcialmente resoluble.

Marca la opción verdadera: f = 〈g|h〉 ⇒ f ∈ REC. f = μ[g] ^ g ∈ T-WHILE ⇒ f ∈ T-WHILE. f = μ[g] ^ f ∉ F(WHILE) ⇒ g ∉ F(WHILE).

El problema H^1. es resoluble pero no es totalmente resoluble. es totalmente no resoluble. es parcialmente resoluble.

La función god es. sobreyectiva pero no inyectiva. biyectiva pero no recursiva. biyectiva y recursiva.

Marca la opción verdadera: WHILE ⊂ WHILE_A. WHILE = WHILE_A. F(WHILE) ⊆ F(WHILE_A).

Si a la definición de la función castor afanoso le añadimos que Σ(0)=0 entonces. Σ ∈ TREC. Σ es una función total pero no recursiva. la función Σ no es ni total ni recursiva.

Un predicado es decidible. si es enumerable. sí y sólo si su función característica asociada es parcial. si se puede encontrar su valor de verdad cualesquiera que sean los argumentos.

Elija la opción correcta: Todo conjunto perteneciente al conjunto potencia de los naturales es un conjunto enumerable. Todo conjunto perteneciente al conjunto potencia de los naturales es un conjunto decidible. Un conjunto perteneciente al conjunto potencia de los naturales puede no ser enumerable ni decidible.

Elige la opción correcta: F(n,p,s) = F(n+i,p+i,s), donde p=max{n,k} con k=max{m∈Σ+d|Xm≺s}. F(n,p,s) = F(n,p+i,s), donde p=max{n,k} con k=max{m∈Σ+d|Xm≺s}. F(n,p,s) = F(n+i,p,s), donde p=max{n,k} con k=max{m∈Σ+d|Xm≺s}.

Toda indexación de funciones es. biyectiva. sobreyectiva. invertible.

El predicado H1 es parcialmente resoluble. porque es el predicado asociado a la función computable f=σ(U[REC1]). porque es el predicado asociado a la función Σ. porque no es resoluble.

Elija la opción correcta: U[RECn]∈RECn+1. U[REC1] es una función total. U[RECn]∈RECn.

Sea el programa WHILE Q = (1, 1, X1:=X1+1;X1:=X1+1). TQ(3) = 2. CALQ(3,2) = (4,5). FQ = σ (con σ ∈ INI).

El cardinal de las funciones computables es: menor que el de las funciones no calculables. menor que el de las funciones totales. mayor que el de las funciones representables.

El conjunto INI es. finito. infinito numerable. infinito no numerable.

∀ Q1 = (1, p1, s1) Q2 = (1, p2, s2) x | FQ1(x), FQ2(x) tam(s1) > tam(s2). TQ1(x) > TQ2(x). FQ1(x) < FQ2(x). las otras dos opciones son falsas.

Si Q WHILE. la función SIGQ es una función total. la función SIGQ puede, para ciertos valores de su argumento, no estar definida. la función SIGQ no está definida para configuraciones terminales.

Dados los conjuntos PRED(T-WHILE) y PRED(WHILE), se verifica que. PRED(T-WHILE) y PRED(WHILE) son conjuntos mutuamente excluyentes. PRED(T-WHILE) ⊂ PRED(WHILE). PRED(T-WHILE) ⊃ PRED(WHILE).

Que un conjunto sea Turing-decidible significa que. Alan Turing decidió que dicho conjunto merecía ser analizado. existe una función Turing-calculable que enumera el cojunto en un tiempo finito. el complementario de dicho conjunto es también decidible.

Sea M la MT especificada por la tabla 0 * 1 0 r 0 1 * r 2 1 r 2 2 * h 2 2 h 2. un método de operación de M es ( ...* w_*... ) * ( ...* w_ * ... ). un método de operación de M es ( ...* _ *... ) * ( ...* _*... ). ( ...* w _*... ) ⊢* ( ...* w ｜_*... ).

Un predicado enumerable es también. decidible. generable. niguna de las otras opciones es cierta.

Un predicado de PRED(T-MT) es un predicado. decidible. cuyo valor de verdad no está definido para algunos argumentos. niguna de las otras opciones es cierta.

Σ(n) es. la función castor afanoso. una función computable. una función no representable.

¿Qué afirmación es correcta?. Σ(n) > Σ(n+1). Σ(n) < Σ(n+1). Σ(n) = Σ(n+1).

Una función f es WHILE-computable si y solo si: puede representarse con una MT. : ).

La longitud de un programa WHILE: puede coincidir con su tamaño. : ).

El problema de la parada para programas con una entrada (dado por el predicado H1): es parcialmente resoluble. : ).

ɏ Q ϵ WHILE: t. tam(Q) ≥ long(Q). : ).

Si g: Nk → N ˄ h: Nk+2 → N ˄ f =<g|h> ˄ FQ = f. Q = (k+1,k+3,s). : O.

Si g: Nk+1 → N ˄ f=u[g] ˄ f =<g|h> ˄ FQ. : Q = (k+1,k+3,s). : ).

El predicado H1 es parcialmente resoluble: es el predicado asociado a la función computable f = σ(U[REC1]). :).

Si σ^2_1(3,4) =32 entonces: codi(X4 := X5 - 1) = 163. Obvio.

Marcar la afirmación verdadera: Un problema no resoluble va asociado a un predicado no decidible. Esta no es verdadera.

Configuración a la que transita (2,2,X1:=0;X2=X1) desde (2,0,3) es entonces. (3,0,0). .

Q = (1,1, while X1 0 do X1 := 0 od) entonces. T (x) está definida siempre. .

- Una computación completa de una máquina de Turing puede tener una longitud. mayor que su número de estados. .

¿Cuál de estas MT realiza el método de operación: …*(1)w*... => …*1w(*)..., si w T*?. ( q_0 * h q_0) , ( q_0 1 r q_0 ). .

Si un predicado es T-enumerable, entonces. existe una MT que para tras un número finito de pasos, si dicho predicado es cierto para los argumentos. .

Si un conjunto es recursivamente decidible, entonces. es recursivamente generable. .

Si un predicado es T-decidible, entonces. existe una función total T-calculable que es su función característica. .

TREC es. conjunto de funciones matemáticas recursivas totales. .

TQ(x) = 3 si. Q = (1, 3, X1:=X2+1;X3:=X1-1). .

La función calculada por (1,2,X1:=X2;X2:=X1+1) es. la función constante 0. .

¿Cuál de estos vectores es configuración válida del programa WHILE(2,2,X1:=0,X2:=X1)?. (2, 1, 7). .

Una MT realiza la transición ( q_2,..*101*...,7) |- ( q_5,...*1(0)1*...,6) porque su tabla contiene la línea: ( q_2 1 l q_5 ). .

f ∈ TREC^m. P es resoluble, tal que REC incluye función que pueden representarse con MT. .

Se cumple que Fq = ø si : Q = (0 , 0, X_1 := 0). Q = (1 , 1, X_1 := 0). Q = (0 , 1, X_1 := 0).

El predicado H^n tiene. n + 1 argumentos. n argumentos. dos argumentos.

El programa Simular que aparece en el programa Universal tiene. un unico argumento. puede tener tres o mas argumentos. dos argumentos.

Marca la afirmacion verdadera: Un predicado no resoluble va asociado a un problema no decidible. Un problema no resoluble va asociado a un predicado no decidible. Un problema no resoluble va asociado a un predicado no enumerable.

Sean Q y R dos proggrramas WHILE distintos de 1 argumento, entonces. Fq (x) ≠ Fr(y),∀ x,y ∈ N. /Fq (x), Fr) ∈ N^2, ∀ x,y ∈ N. CODI (Q) ≠ CODI (R).

En el lenguaje While ampliado los comentarios: solo se pueden escribir en lineas vacias. se pueden escribir al inicio de una linea de codigo. se pueden escribir al final de una linea de codigo.

Si g: N^k+1 --> N ^ f = u[g] ^ Fq = f entonces: Q = (k, k, s). Q = (k + 1, k + 1, s). Q = (k, k+1, s).

La funcion castor afanoso es una función que: ∈ F(MT). es parcialmente resoluble. ∉ REC.

Elige la opcion correcta: Toda función total es una función computable. El cardinal del conjuto T-REC es el mismo que el cardinal del conjunto REC. Toda función computable es una funcion total.

Elija la opción correcta: Toda funcion total es una funcion computable. El cardinal del conjunto T-REC es el mismo que el cardinal del conjunto REC. Toda funcion computable es una funcion total.

TREC es: un subconjunto propio de las funciones recursivas. F(WHILE). el conjunto de todas las funciones recursivas.

La funcion degod es: recursiva y total. recursiva y parcial. no computable.

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 -> N. U[REC^n] : N^(n+1) ->.

El programa Simular (z,m) que aparece en el programa Universal. permite ejecutar las sentencias de asignacion del programa m con entrada. puede tener dos o mas argumentos. simula el funcionamiento del programa z con la memoria m.

La funcion castor afanso (Σ(n)). esta definida como la funcion que devuelve el mayor valor de todos los que devuelven los programas WHILE de una entrada de longitud n cuando dicha entrada vale n. no puede definirse de forma matematicamente correcta porque la funcion no es computable. esta definida como la funcion que devuelve el mayor valor de todos los que devuelven los programas WHILE de una entrada de longitud n cuando dicha entrada vale 0.

Elige la opcion correcta: U[REC^n] ∈ REC^n. U[REC^1] es una funcion total. U[REC^n] ∈ REC ^ (n+1).

La funcion castor afanoso es una funcion que: ∈ F(MT). ∉ REC. es parcialmente resoluble.

La funcion universal U (z, _x): ninguna de las otras opciones es correcta. devuelve la salida del programa (n,max{n,k},Decodi(z)) para el vector de entrada _x. devuelve el codigo del programa (n, max{n,k}, DeCodi(z)) para el vector de entrada _x.

Marca la afirmacion verdadera. WHILE_A ⊆ WHILE. F(WHILE_A) = F(WHILE). WHILE_A = WHILE.

La funcion Castor afanoso esta definida como: Σ(n) = max {Q(0) | ∈ WHILE^n y Q ∈ P^1 y Q(0) ∈ N}. Σ(n) = max {Q(n) | Q ∈ WHILE^n y Q ∈ P^1 y Q(0) ∈ N}. Σ(n) = max {Q(0) | Q ∈ WHILE^n y Q ∈ P^n y Q(0) ∈ N}.