Si a la definición de la función "Castor afanoso (Σ)" le añadimos que Σ(0) = 0. ¿Es una función total? ¿Y recursiva?	Σ es una función total pero no recursiva.
¿Qué hace 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.
¿Qué calcula el programa Universal U(z,x̲)?	El valor de salida del programa (n,max{n,k},DeCodi(z)) para el vector de entrada x̲
Sea REC^m el conjunto de funciones recursivas de N^n a N. La función universal U[REC^m] verifica: a) U[REC^m] : N^2 -> N b) U[REC^m]: N^(n+1) -> N c) U[REC^m]: N^n -> N	Verifica U[REC^m]: N^(n+1) -> N
¿La función god es recursiva y parcial?	No. Es recursiva, pero no parcial.
¿La función god es biyectiva y recursiva?	Sí.
¿La función degod es total?	Sí.
¿La función degod es recursiva?	Sí.
¿La función degod es biyectiva?	No.
¿La función Castor afanoso es una función Turing-computable?	No.
Verdadero o falso: El cardinal de T-REC es igual al cardinal de REC.	Verdadero
Verdadero o falso: Todo conjunto decidible es enumerable	Verdadero
Verdadero o falso: Toda función total es computable	Falso
Dado el código s: While X1 != 0 do: x1 := 0 od ¿Cuánto es codi(s)?	codi(s) = 4
¿Es el predicado H^1 enumerable?	Sí, porque es el predicado asociado a una función recursiva.
¿El cardinal de F(WHILE) coincide con el de REC-TREC?	Correcto
¿El cardinal de F(WHILE) es infinito no numerable?	No
Una función f es WHILE-computable si y solo si:	puede representarse con una MT / existe un programa WHILE Q \| FQ = f
Si codi(s) = 50, entonces ¿cuánto vale Codi(s)?	Codi(s) = god(s) - 1
¿Porqué el predicado H^1 es parcialmente resoluble?	Porque es el predicado asociado a la función computable f = σ(U[REC^1])
Dada la función Castor Afanoso (Σ), se cumple que:	si m > n => Σ(m) > Σ(n), con m,n pertenecientes a N
¿La función reemplazar del programa universal (reem) es una función total?	Sí.
¿La función reemplazar del programa universal (reem) es una función inyectiva?	No.
¿La función reemplazar del programa universal (reem) es una función parcial de 3 argumentos?	No, es una función total.
Dado el codigo s: while x1 != 0 do x1 = 0 od ¿codi(s)?	codi(s) = 4
¿Σ(6) = Σ(5)?	No.
¿Σ(6) = 2*Σ(3)?	Sí.
La máquina de Turing universal tiene como entrada	una maquina de Turing y sus argumentos
Sabemos que WHILE c WHILE_A y que	F(WHILE_A) = F(WHILE)
Si el problema de la parada fuera resoluble, entones se verificaría que	Σ ∈ TREC
¿Qué calcula el programa Universal U(z,x)?	El valor de salida del programa (n,max{n,k},DeCodi(z)} para el vector de entrada x
Sea REC^n el conjunto de funciones recursivas de N^n en N. La función universal U[REC^n] verifica:	U[REC^n] : N^n+1 --> N
Si la definición de la funcion Castor afanoso le añadimos que Σ(0) = 0, entonces ¿Σ pertenece a T-REC?	Noo
Si la definición de la funcion Castor afanoso le añadimos que Σ(0) = 0, entonces ¿Σ es una función recursiva?	No, es una función total pero no recursiva.
La función degod es:	biyectiva y recursiva
Segun el teorema de equivalencia:	f ∈ REC --> ∃Q∈ WHILE: Fq= f
¿Es cierto que N^2 ∈ N*?	No.
¿Es cierto que N c N*?	Sí.
¿Es cierto que () no está contenido en N*?	No.
F(WHILE) es un conjunto con cardinal	Igual que REC-TREC
¿Es el predicado H^1 RECURSIVAMENTE enumerable?	Pos si.
Un problema es no resoluble si	No se puede definir en base a un predicado decidible
Determina que Q perteneciente a WHILE verifica FQ = σ (σ (pi(4,2))	Q = (4,4,X1=X2;X1=X1+1;X1=X1+1)
Dado Q = (), ¿FQ pertenece a REC?	Si.
La codificación de Cantor de N^3 establece:	Una biyeccion entre N y N^3
Del teorema de equivalencia se concluye que	REC = F(WHILE)
La función god es	Biyectiva y recursiva
Q = (2,s) perteneciente a WHILE ^ \|s\|do + \|s\|:= = 1 si:	s = X5001 = X129
El natural 55 codifica la sentencia	X12 = 0
¿La estructura de control if–then–else–fi permite definir funciones no representables en WHILE?	No
¿ INI ⊆ T–WHILE ?	Si
¿Toda función total WHILE-computable pertenece a TREC?	Si
¿ REC ⊆ F(WHILE) ?	Si
¿Si Q es un programa WHILE que no acaba para alguna entrada entonces se cumple que FQ ∈ (REC – TREC) ?	Si
¿El operador de recursión primitiva puede expresarse en el modelo WHILE?	Si
¿ \|\| ( F(WHILE) – TREC ) \|\| ≥ ℵ0 ?	Si
¿La función decodi es sobreyectiva?	No
¿Toda indexación de funciones es biyectiva?	No
¿El programa Añadir tiene dos entradas?	Si
¿La función universal para REC1 es total?	No
¿La función CODI es sobreyectiva?	Si
¿El programa Ejecutar tiene dos entradas?	Si
¿La función Codi es total?	Si
¿La función DECODI es total?	Si
¿La función codi es total?	No
¿La función CODI es total?	Si
¿La función DeCodi es inyectiva?	Si
¿La función DeCodi es sobreyectiva?	Si
¿La función decodi es total?	Sí. Puesto que la función codi es sobreyectiva.
¿La función reemplazar del programa universal ( reem ) es biyectiva?	No. Si el segundo argumento es cero, el valor de la función es el primer argumento, independientemente del tercer argumento, por lo que hay vectores distintos que devuelven el mismo valor.
¿La función tipo es total?	Sí. La función módulo lo és.
¿La función tipo es biyectiva?	No. Puesto que no es inyectiva.
¿d(σ21(x,0)) = x ?	Sí. El par (x,0) está en la diagonal x , que es precisamente lo que devuelve la función d cuando se aplica a su cantorización.
¿La función DECODI es biyectiva?	Sí. Ya que es inyectiva y sobreyectiva.
¿La función tipo es sobreyectiva?	Sí. La función módulo lo és.
¿La función Codi es inyectiva?	Sí. Si dos códigos son distintos sus números también lo son.
¿La función CODI es biyectiva?	Si.
¿Si x > y entonces σ21(x,y) > σ21(y,x) ?	No. Es justamente al contrario, σ21(x,y) < σ21(y,x), ya que es la segunda componente la que se suma en la expresión de la cantorización.
¿La función DECODI es inyectiva?	Sí. Puesto que la función CODI es biyectiva.
¿La “gödelización” de los programas WHILE asocia a éstos naturales de forma biyectiva?	Si.
¿La función DeCodi es sobreyectiva?	Sí. Puesto que la función Codi es biyectiva.
¿La función DECODI es sobreyectiva?	Sí. Puesto que la función CODI es biyectiva.
¿El programa Simular tiene dos entradas?	Sí. La primera es el número de programa a simular, y la segunda es la memoria, que es la gödelización del vector de entrada.
¿La función universal para RECn pertenece a RECn ?	No. Pertenece a RECn+1.
¿La función Codi es sobreyectiva?	Sí. Todo natural es imagen de algún código.
¿La función DeCodi es biyectiva?	Sí. Ya que es inyectiva y sobreyectiva.
¿Dentro del programa Simular hay una llamada al programa Ejecutar ?	Sí. Cuando el tipo de la sentencia es una asignación.
¿Una indexación siempre es sobreyectiva pero puede no ser inyectiva?	Sí. Para ser indexación sólo se exige que sea sobreyectiva.
¿Si Q = (1, p, s) es un programa WHILE que calcula una función total entonces ∀x∈N TU (Codi(s), x) > TQ(x) ?	Sí. Puesto que el progama universal debe gödelizar y degödelizar antes de simular, lo cual incrementa el número de pasos por encima del programa simulado.
¿La función CODI es inyectiva?	Sí. Si dos programas son distintos sus números también lo son.
¿La función degod es biyectiva?	No. Hay una cantidad infinita numerable de entradas distintas de la función degod que devuelven cero.
¿Dentro del programa Añadir hay una llamada a la función god ?	Sí. Con ella devolvemos el valor buscado.
¿El programa Reducir tiene dos entradas?	No. Sólo tiene una, que es la gödelización del código pendiente de ejecución.
¿La función DeCodi es total?	Sí. Puesto que la función Codi es biyectiva.
¿ µ[U[REC15]] ∈ REC15 ?	Sí. Puesto que la función universal añade un argumento, y la minimización no acotada lo quita.
¿La función tipo es inyectiva?	No. El conjunto inicial es infinito y el final finito, por lo que no puede ser inyectiva.
¿La función reemplazar del programa universal ( reem ) es total?	Sí. Siempre devuelve un natural.
¿La función universal para TREC2 es total?	Sí. Puesto que todas las funciones de TREC2 son totales por definición.
¿La función reemplazar del programa universal ( reem ) es sobreyectiva?	Sí. Si el segundo argumento es cero, el valor de la función es el primer argumento, que puede ser cualquier natural.
¿La función decodi es biyectiva?	No. Puesto que no es sobreyectiva.
¿Dentro del programa Ejecutar hay una llamada al programa Reducir ?	No. Hay llamadas a la funciones tipo , reem , extr y degod .
¿Si n es el número de un programa que suma dos naturales entonces la función U[REC2](n, x, y) puede diverger?	No. La suma de dos naturales siempre es otro natural, nunca diverge.
¿Si L(x) > L(y) entonces god(x) > god(y) ?	No. Por ejemplo, god(0,0) < god(1) .
¿Dentro del programa Reducir hay una llamada al programa Ejecutar ?	No. Hay llamadas a la funciones god y degod .
¿La función Codi es biyectiva?	Sí. Ya que es inyectiva y sobreyectiva.
¿La función codi es sobreyectiva?	Sí. Todo natural es imagen de alguna sentencia.
¿El tamaño de un programa WHILE puede ser el doble que su longitud?	No. Puesto que todo programa WHILE tiene al menos una sentencia de asignación, aunque tengamos bucles anidados, nunca el tamaño puede alcanzar el doble de la longitud.
¿Si un problema es no resoluble el predicado del que es asociado puede ser enumerable?	Sí. Puesto que un predicado puede ser no decidible y ser enumerable.
¿Toda función total es computable?	No. Por ejemplo, la función castor afanoso es total y no es computable.
¿Todo problema asociado a un predicado enumerable es resoluble?	No. Puesto que un predicado puede ser enumerable y no ser decidible.
¿ ∑(2) = 2 ?	Sí. Para una longitud de 2 podemos tener un bucle y una asignación. O bien dos asignaciones. En el primer caso, dado que queremos incrementar la variable X1 , si entramos en el bucle nunca terminaríamos, y si no entramos la salida será cero. En el segundo caso, el mayor número que podemos devolver en X1 se consigue con dos asignaciones de incremento consecutivas de dicha variable, lo que nos da un valor de dos como respuesta.
¿Si un programa WHILE no tiene bucles, entonces la longitud y el tamaño siempre coinciden?	Sí. Ya que en este caso el número sentencias y el de líneas es el mismo.
¿El tamaño de un programa WHILE puede ser mayor que su longitud?	Sí. Si el programa tiene algún bucle entonces el tamaño del programa es mayor que su longitud.
¿El problema de la parada es totalmente no resoluble?	No. Es parcialmente resoluble.
¿ ∑(n+1) > ∑(n) ∀n∈N ?	Sí. Proposición 13.8.
¿Si un problema es resoluble entonces el predicado del que es asociado es enumerable?	Sí Puesto que todo predicado decidible es enumerable.
¿ ∑(3) = 3 ?	Sí. Para una longitud de 3 podemos tener dos bucles y una asignación. O bien un bucle y dos asignaciones. O bien tres asignaciones. En el primer caso deben de ir anidados, pero dado que queremos incrementar la variable X1 , si entramos en los dos bucles nunca terminaríamos, y si no entramos la salida será cero. En el segundo caso, dado que todas las variables al inicio valen cero, estamos en la misma situación si las dos asignaciones están dentro del bucle, o bien no acaba o devuelve cero. Si una la colocamos fuera del bucle, sólo podríamos incrementar en uno la variable X1 . En el tercer caso, el mayor número que podemos devolver en X1 se consigue con tres asignaciones de incremento consecutivas de dicha variable, lo que nos da un valor de tres.
¿El predicado H pertenece a PRED(REC) ?	Sí. Ya que es parcialmente resoluble, al igual que H1 .
¿ ∑(1) = 1 ?	Sí. Para una longitud de uno, sólo podemos tener una asignación. Dado que queremos incrementar la variable X1 , el mayor número que podemos devolver en X1 se consigue con una asignación de incremento de dicha variable, lo que nos da un valor de uno.
¿La longitud de un programa WHILE puede ser mayor que su tamaño?	No. Sólo puede ser igual o menor.
¿El predicado H pertenece a PRED(REC) ?	Sí. Ya que es parcialmente resoluble, al igual que H1 .
¿El tamaño de un programa WHILE siempre es mayor que su longitud?	No. Si el programa no tiene ningún bucle entonces la longitud y el tamaño coinciden.

Descubre

Crear Tarjetas

Acerca de Nosotros

Explore Tarjetas

Comparta este Set de Tarjetas de Aprendizaje

Talf Bloque 4

Cómo estudiar sus tarjetas

Rango de Cartas a estudiar

122 Cartas en este set