¿La idea de número es anterior a la escritura?	Sí, al menos 25000 años anterior.
¿A lo largo de la historia todos los sistemas de numeración han sido en base 10?	No. Los babilonios lo tenían en base 60.
¿La idea de sistema de numeración es anterior al número cero?	Sí. Los sistemas de numeración más antiguos no tenían el cero.
¿La operación raíz cuadrada se inventó en el Renacimiento?	No. Los babilonios ya calculaban raices cuadradas.
¿A lo largo de la historia ha habido algún sistema de numeración en base sesenta?	Sí. Por ejemplo los babilonios lo tenían en base 60.
¿El vocablo algoritmo proviene de la Máquina de Turing?	No. Proviene del nombre Abu Ja´far Mohamed ibn Musa al–Khowârizmî (780–850).
¿El autor de la obra “Ars Magna” fue Raimundo Lulio?	Sí. Sobre el año 1300 escribió esta obra, en la cual se describe un procedimiento general de base combinatoria para hallar todas las verdades.
¿George Boole trabajó en la formalización de la lógica?	Sí. De hecho, la conocida como álgebra de Boole, fue uno de los primeros pasos hacia su formalización.
¿El Teorema de incompletitud de Gödel se publicó después de 1936?	No.
¿El Teorema de incompletitud de Gödel se publicó antes de 1963?	Sí. El año 1936 fue el año en que se formalizó el concepto de algoritmo, y puesto que el Teorema de incompletitud de Gódel fue uno de los trabajos en los que se basaba dicha formalización, su publicación es anterior, concretamente en 1931. Por tanto también es anterior a 1963.
¿Gödel, Hilbert y Ackermann fueron contemporáneos?	Sí. Tanto Gödel, Hilbert como Ackermann coincidieron en 1936, el año de la formalización del concepto de algoritmo, en la cual los tres habían influido.
¿Kleene presentó el concepto de función μ–recursiva en 1936?	Sí. En este año publicó un artí**** con dicho concepto, coincidiendo con otros modelos que se presentaron ese mismo año.
¿El modelo de máquinas de Turing puede representar cualquier función calculable?	Sí. Precisamente una de las definiciones de función calculable es aquella función que puede ser computada por una máquina de Turing.
¿Las MT representan el mismo conjunto de funciones que el modelo URM?	Sí. Las computables.
¿El modelo de funciones recursivas fue propuesto por A. Turing en 1936?	No. Fue propuesto por Kleene. Turing propuso la máquina que lleva su nombre.
¿Un algoritmo conclusivo puede estar compuesto de infinitas instrucciones?	No. Un algoritmo, conclusivo o no, siempre es una secuencia finita de instrucciones.
¿Un algoritmo no conclusivo puede estar compuesto de infinitas instrucciones?	No. Un algoritmo, conclusivo o no, siempre es una secuencia finita de instrucciones.
¿Un algoritmo no conclusivo puede estar compuesto de un número finito de instrucciones?	Sí.
¿El modelo RAM fue propuesto después que el lambda cálculo?	Sí. El modelo RAM (Random Access Machine) es del año 1974, mientras que el lambda cálculo es una de las cuatro formalizaciónes del concepto de algoritmo del año 1936.
¿El modelo URM es anterior al modelo RAM?	Sí. El modelo RAM (Random Access Machine) es del año 1974, mientras que el lambda cálculo es una de las cuatro formalizaciónes del concepto de algoritmo del año 1936.
¿Se puede demostrar que WHILE y Pascal son modelos equivalentes?	Sí. Con un modelo de cómputo podemos representar a todas las funciones computables, que son precisamente las que puede calcular cualquier lenguaje de programación como Pascal.
¿Todo conjunto infinito numerable es enumerable?	No. Hay una cantidad infinita no numerable de conjuntos infinitos numerables, mientras que enumerables sólo hay una cantidad infinita numerable. Esto se debe a que cada uno tiene un algoritmo asociado, y la cantidad de algoritmos es infinita numerable.
¿Una tabla de una MT puede tener un número impar de filas?	Sí. Si el número de símbolos es par y el número de estados es impar entonces la MT tendrá un número impar de filas, ya que el producto de dos números impares siempre es impar.
¿En la cuarta columna de la tabla de una MT siempre hay elementos repetidos?	Sí. Ya que en una MT hay al menos 2\|\|K\|\| filas y sólo hay \|\|K\|\| estados.
¿Una tabla de una MT puede tener sólo una fila?	No. Al menos debe tener dos, ya que un alfabeto no puede ser vacío.
¿En la tercera columna de una MT siempre hay elementos repetidos?	No. Por ejemplo, en una MT de un estado hay n+1 filas y n+4 elementos posibles en esas filas, por lo que pueden no repetirse los elementos.
¿El conjunto de configuraciones de una MT siempre es finito?	No. Siempre es infinito, ya que tanto el conjunto de expresiones de cinta como el de cuadrados escrutados posibles para una MT son infinitos.
¿La expresión de cinta de una MT es una aplicación biyectiva?	No. Dado que es una aplicación de un conjunto infinito en un conjunto finito nunca puede ser biyectiva.
¿La función E : Z → { a0 , a1 } , E(n) = a1 ∀n∈Z es una expresión de cinta de alguna MT?	No. El número de cuadrados no vacíos en una expresión de cinta de una MT siempre ha de ser finito.
¿El conjunto de configuraciones de una MT siempre es infinito?	Sí. Puesto que tanto el conjunto de expresiones de cinta como el de cuadrados escrutados posibles para una MT son infinitos.
¿El conjunto de configuraciones iniciales de una MT siempre es infinito?	Sí. Puesto que tanto el conjunto de expresiones de cinta como el de cuadrados escrutados posibles para una MT son infinitos, y estado inicial siempre hay uno.
¿El conjunto de configuraciones terminales de una MT siempre es infinito?	No. Si en la tercera columna de una MT no aparece ninguna “h” entonces el conjunto de configuraciones terminales es vacío.
¿El conjunto de configuraciones no terminales de una MT siempre es infinito?	No. Si todos y cada uno de los elementos de la tercera columna de una MT es una “h” entonces el conjunto de configuraciones no terminales es vacío.
¿En toda MT se cumple que \|\|{ z ∈ Z \| E(z) ≠ a0 }\|\| ∈ N ?	Sí. El número de cuadrados no vacíos en una expresión de cinta de una MT, por definición, siempre ha de ser finito.
¿En una MT una configuración puede ser a la vez inicial y terminal?	Sí. Toda configuración terminal que cuyo estado sea el inicial es también configuración inicial.
¿La función E : Z → { a0 , a1 } , E(n) = a0 ∀n∈Z es una expresión de cinta de alguna MT?	Sí. Nos indica que la cinta está vacía, lo cual es perfectamente válido.
¿Una expresión de cinta de una MT es una aplicación?	Sí. Por definición, es una aplicación con ciertas restricciones, pero siempre es una aplicación.
¿En una MT, [ (q, E, z) \|— (q´, E´, z´) ] ⇒ [ z’ < z+2 ] ?	Sí. En un paso, una MT no puede moverse más de un cuadrado a la derecha (ni a la izquierda).
¿En una MT, [ (q, E, z) \|— (q´, E´, z´) ] ⇒ \|\|{ n∈ Z \| E(n)≠E’(n) }\|\| ≤ 1 ?	Sí. En un paso, una MT no puede escribir en más de un cuadrado.
¿En una MT, una computación puede tener logitud cero?	Sí. En ese caso tiene una sola configuración.
¿En una MT, toda computación terminada es bien iniciada?	No. La última configuración de una computación puede ser terminal sin que la primera sea inicial.
¿En una MT, toda computación bien iniciada es terminada?	No. La primera configuración de una computación puede ser inicial sin que la última sea terminal.
¿El conjunto de computaciones bien iniciadas de una MT siempre es infinito?	Sí. Dado que el conjunto de configuraciones iniciales de una MT siempre es infinito.
¿El conjunto de computaciones terminadas de una MT siempre es infinito?	No. Puesto que el conjunto de configuraciones terminales de una MT puede ser vacío.
¿El conjunto de computaciones completas de una MT siempre es infinito?	No. Ya que el conjunto de configuraciones terminales de una MT puede ser vacío.
¿Existe una MT M tal que: (M se para a partir de C) ∧ (M no se para a partir de C’) ∧ (C \|— C’)?	No. Ya que si se cumplen las dos primeras proposiciones de la conjunción, la tercera no se puede cumplir.
¿Una MT puede pararse detrás de la cadena vacía con la cinta completamente vacía?	Sí. En realidad sólo se exige que la semicinta izquierda a partir del cuadrado escrutado en que se ha parado, incluido éste, esté vacía.
¿La función cero es Turing-computable?	Sí.
¿La función sucesor es Turing-computable?	Sí.
¿La función identidad es Turing-computable?	Sí.
¿La función suma es Turing-computable?	Sí.
¿Al colocar una MT detrás de una cadena siempre el cuadrado escrutado está vacío?	Sí. Dicho cuadrado es el inmediatamente a la derecha de la cadena, y por definición, tanto él como los restantes que no forman parte de la cadena están vacíos.
¿La función resta es Turing-computable?	Sí.
¿Existen funciones no computables que pueden representarse con MT?	No. Precisamente una de las definiciones de función computable es aquella función que puede ser computada por una MT, en cuyo caso dicha MT la representa.
¿La función doble es Turing-computable?	Sí.
¿Para cualquier MT podemos encontrar un AFND equivalente?	No. Si fuera así, un AFND podría reconocer cualquier lenguaje decidible, y no es el caso, sólo reconoce los lenguajes de tipo 3.
¿La función mitad es Turing-computable?	Sí.
¿Si dos MT computan la misma función, entonces tienen el mismo número de estados?	No. Si tenemos una MT que es igual a otra salvo en que la segunda tiene algunos estados adicionales, todos ellos inaccesibles, tendremos un ejemplo de dos MT que tienen distinto número de estados y que, sin embargo, computan la misma función. Esta forma trivial no es la única en que puede darse esta situación, pero es suficiente para mostrar que la respuesta a esta pregunta es negativa.
¿Una MT puede decidir si una cadena pertenece a un LCL?	Sí. Dado que hay un autómata que puede decidirlo, y puesto que el modelo de MT es más potente que cualquier autómata, la respuesta es afirmativa.
¿El conjunto de los números pares es Turing-decidible?	Sí.
¿Si un predicado es decidible, entonces también es enumerable?	Sí. Puesto que TREC está incluido en REC.
¿El conjunto de los números múltiplos de 3 es Turing-decidible?	Sí.
¿Si un predicado es enumerable, entonces también es decidible?	No. Dado que REC no está incluido en TREC.
¿Una MT puede realizar procesos infinitos no periódicos?	Sí. El funcionamiento de una MT viene determinado, además de por su tabla, por el contenido de la cinta, la cual no está acotada. Esto hace que pueda darse el caso en que nunca se repita una configuración por muy larga que escojamos la computación.
¿Los términos “funciones recursivas” y “funciones recursivas primitivas” son equivalentes?	No. Las funciones recursivas incluyen de manera propia a las recursivas primitivas, ya que estas últimas se definen igual que las primeras salvo por el hecho de que no tienen el operador de minimización no acotada (por lo que son todas funciones totales).
¿La función inicial cero tiene cero argumentos?	Sí. Por definición.
¿El conjunto INI es infinito numerable?	Sí. Dado que contiene las proyecciones, que es un conjunto infinito numerable.
¿Existe una función recursiva de cero argumentos que no puede definirse por recursión primitiva?	Sí. La función de cero argumentos que siempre diverge.
¿Si g es una función de k+1 argumentos y g(n,5) = 0 entonces μ[g](n) ≠ 0 ?	No. Si g(n,0) = 0 entonces μ[g](n) = 0 .
¿La minimización no acotada de una función perteneciente a TREC pertenece a TREC?	No. Es precisamente es el operador de minimización acotada el que nos permite obtener funciones parciales a partir de funciones totales. Así, por ejemplo, la función μ[suma] no pertenece a TREC, a pesar de que suma sí.
¿Si ∃μ[g] y g∈REC entonces μ[g]∈REC ?	Sí. Por definición de REC.
¿Si ( f, g, h: N → N ) ∧ ( f, g ∈ REC ) ∧ ( ∀n∈N, f(2n) = h(2n) ∧ g(2n+1) = h(2n+1) ) entonces h∈REC?	Sí. Puesto que podemos calcular la función h tanto en los argumentos pares como en los impares con una función recursiva, la función h también lo es.
¿Si una biyección es recursiva entonces su inversa es recursiva y total?	Sí. La inversa es total, ya que todo elemento ha de ser imagen de uno y sólo uno, y es recursiva ya que sólo necesitamos para cada valor de la entrada de la inversa, hacer un bucle sobre la función original recorriendo los naturales hasta encontrar de quién es imagen el valor dado.
¿Si una función de cero argumentos es recursiva entonces pertenece a TREC?	No. Si una función de cero argumentos es recursiva entonces, o bien es una función constante (en cuyo caso sí pertenece a TREC), o bien es la función que siempre diverge de cero argumentos (en cuyo caso no pertenece a TREC).
¿Si ∀n∈Nk, ∃t∈N \| g(n,t) = 0 con g∈TREC k+1 , entonces μ[g] ∈ TREC?	No. Ya que puede diverger para valores menores que t .
¿El conjunto de valores de verdad de un predicado puede ser vacío?	Sí. Cuando el predicado es siempre falso.
¿Si g,h∈TREC y f = 〈g\|h〉 entonces f∈TREC?	Sí. La recursión primitiva, si las funciones en las que se basa son totales, siempre es total, y por definición de REC, si dichas funciones son recursivas, ella también.
¿ \|\| ( REC – TREC ) \|\| = ℵ0 ?	Sí. El conjunto REC es infinito numerable, y cualquier subconjunto infinito de un conjunto numerable es infinito numerable.
¿La función suma de dos naturales puede definirse sólo con el operador de composición?	No. Debido a que la extensión de la composición depende de los argumentos, por lo que necesitamos la recursión primitiva.
¿En la expresión abreviada de una función sólo aparecen funciones iniciales y operadores?	No. Pueden aparecer otras funciones recursivas.
¿En la expresión abreviada de una función todas las funciones que aparecen son recursivas?	Sí. Por definición.
¿En la expresión completa de una función sólo aparecen funciones iniciales y operadores?	Sí. Por definición.
¿Los predicados asociados a dos funciones distintas pueden ser iguales?	Sí. Hay muchas formas distintas de ser mayor que cero (y dos de no serlo).
¿Si un conjunto es vacío su función característica siempre vale uno?	No. Siempre vale cero.
¿La función característica de un predicado siempre es total?	Sí. Por definición siempre vale cero o uno.
¿Si la función característica de VP es recursiva, entonces P es decidible?	Sí. Puesto que la función característica de un conjunto, por definición, siempre es total, si además es recursiva entonces pertenece a TREC, por lo que el predicado P es decidible.
¿La función característica de cualquier predicado decidible es una función total?	Sí. Es una función total y computable.
¿Si V es un conjunto recursivamente decidible, entonces XV ∈TREC?	Sí. Puesto que la función que hace decidible a V pertenece a TREC, XV también.
¿Si f ∈REC entonces Pf es enumerable?	Sí. Por definición de predicado recursivamente enumerable.
Calcular la minimización no acotada de la función recursiva suma, siendo suma : N2 → N, donde suma(n, m) = n + m.	μ[ suma ] = uncero
¿Todo predicado P∈PRED(REC) define un conjunto enumerable?	Sí. Concretamente VP .
Calcular la minimización no acotada de la función recursiva resta, siendo resta : N2 → N, donde resta(n, m) = maximo { n – m, 0 }.	μ[ resta ] = π1,1 (función identidad)
Calcular la minimización no acotada de la función recursiva producto, siendo producto : N2 → N, donde producto(n, m) = n * m.	μ[ producto ] = C1,0 (arriba el 1 y abajo el 0)
¿ A∈DECI ⇒ A∈ENUM ?	Sí. Ya que PRED(TREC) ⊂ PRED(REC) .
Calcular la minimización no acotada de la función recursiva división, siendo division : N2 → N, donde division(n, m) =  n / m .	μ[ división ] = ↑
¿ (1, 2, X3:=0 )∈WHILE ?	No. Un programa con dos variables en total no puede tener la variable X3 en su código.
¿Existen ℵ1 programas WHILE diferentes?	No. Puesto que todo programa es representable, sólo hay una cantidad infinita numerable de programas.
¿la función cero es WHILE-computable?	Sí.
¿Un programa WHILE puede tener infinitas variables?	No. Por definición, la seguna componente de la terna que define un programa WHILE, que indica cuantas variables tiene el programa, es un natural, por lo que el número de variables siempre es finito.
¿Si s = s1 ; s2 con s1 , s2 ∈ Cód_While entonces tam(s) > tam(s1) ?	Sí. Puesto que un código siempre tiene al menos tamaño uno, y el tamaño de una secuencia es la suma de los tamaños de sus códigos.
¿La función predecesor es WHILE-compatible?	Sí.
¿ tam(s) > n ⇒ línea(s, n) = 0 ?	No. La función línea nunca devuelve cero. Devuelve el texto de una línea concreta de un código While, o bien la cadena vacía si el número de línea no es válido.
¿∃n∈N–{0} ∧ ∃s∈Cód_While \| salto(s,n) = n ?	No. La función salto , por definición, nunca devuelve la misma línea de la que parte.
¿La función sucesor es WHILE-compatible?	Sí.
¿Algún programa WHILE tiene un número finito de configuraciones iniciales?	Sí. Todo programa WHILE de cero entradas sólo tiene una configuración inicial.
¿Si Q=(n,p,s) es un programa WHILE entonces N^(p+1) = CQ ?	No. Ya que el número de valores posibles para la primera componente es finito.
¿Una configuración de un programa WHILE puede ser a la vez inicial y terminal?	No. Una configuración inicial siempre tiene como primera componente un uno, mientras que una configuración terminal tiene como primera componente como mínimo un dos.
¿la función identidad es WHILE-computable?	Sí.
¿∀s∈Cod_While ∀n∈N, salto(s,n) > n ⇒ línea(s,n) = while Xi ≠0 do ?	Sí. Si la función salto da como resultado un número mayor que la línea en que está, entonces no puede ser una asignación, que daría cero, ni un fin de bucle, que daría un número menor, por lo tanto sólo puede ser una cabecera de bucle.
Demostrar constructivamente que la función suma es WHILE-computable.	Sea el programa WHILE Q = (2, 2, s) con s: while X2 ≠ 0 do X1 := X1 + 1; X2 := X2 – 1 od FQ = suma
¿ c1 \|— c2 ⇒ c1 ≠ c2 ?	Sí. El número de línea siempre cambia de una configuración a su siguiente.
¿ ∃Q = (n, p, s) ∈ WHILE \| TQ(x) = 0 con x∈Nn ?	No. La función complejidad temporal o bien diverge, o bien devuelve un natural mayor que cero, pero nunca puede devolver cero ya que todo programa ha de tener alguna sentencia.
Demostrar constructivamente que la función resta natural es WHILE-computable, siendo resta : N2 → N, donde resta(n, m) = maximo { n – m, 0 }	Sea el programa WHILE Q = (2, 2, s) con s: while X2 ≠ 0 do X1 := X1 – 1; X2 := X2 – 1 od FQ = resta
¿ SIGQ(n,x) = (n+1, x) ⇒ línea(s,n) = od con Q∈WHILE , n∈N ?	No. Si el contenido de la línea es od nunca pasa a la línea siguiente en un paso.
¿La función SIG de un programa WHILE siempre es total?	Sí. Precisamente amplía el concepto “transitar directamente” para darnos una función total.
Demostrar constructivamente que la función producto es WHILE-computable, siendo producto : N2 → N, donde producto(n, m) = n * m	Sea el programa WHILE Q =(2, 4, s) con s: Sea el programa WHILE Q = (2, 3, s) con s: X3 := X1; X1 := 0; while X2 ≠ 0 do X1 := suma(X1, X3); X2 := X2 – 1 Od FQ = producto
¿La función SIG de un programa WHILE siempre es sobreyectiva?	No. Ya que puede existir una configuración de un programa WHILE que no sea la siguiente de ninguna otra.
¿La función SIG de un programa WHILE siempre es inyectiva?	No. Dado que si una configuración final es la siguiente de alguna configuración, entonces ésta y la citada final son distintas pero tienen la misma imagen.
Demostrar constructivamente que la función división es WHILE-computable, siendo division : N2 → N, donde division(n, m) =  n / m .	Sea el programa WHILE Q = (2, 3, s) con s: X1 := X1 + 1; while X1 ≠ 0 do X1 := resta(X1, X2); X3 := X3 + 1 od; X1 := X3 – 1 FQ = division
¿La función SIG de un programa WHILE siempre es biyectiva?	No. Puesto que puede no ser ni inyectiva ni sobreyectiva.
¿ ∀Q∈WHILE ∀i∈N, CALQ(x, i) = CALQ(x, i+1) ⇒ TQ(x) ≤ i ?	Sí. Si dos configuraciones consecutivas son iguales significa que en ese número de pasos, o menos, el programa ya ha terminado, por lo que acota la función complejidad temporal.
Demostrar constructivamente que la función potencia es WHILE-computable, siendo potencia : N2 → N, donde potencia(n, m) = nm.	Sea el programa WHILE Q = (2, 3, s) con s: X3 := X3 + 1; while X2 ≠ 0 do X3 := producto(X3, X1); X2 := X2 – 1 od; X1 := X3 FQ = potencia
¿La función CAL de un programa WHILE siempre es total?	Sí. Puesto que el número de pasos siempre es finito.
¿La función CAL de un programa WHILE siempre es sobreyectiva?	No. Nunca lo es, ya que siempre hay vectores que no son configuraciones del programa.
Demostrar constructivamente que la función factorial es WHILE-computable, siendo factorial : N → N, donde factorial(n) = n!.	Sea el programaWHILE Q = (1, 2, s) con s: X2 := X1 – 1; while X2 ≠ 0 do X1 := producto(X1, X2); X2 := X2 – 1 od FQ = factorial
¿La función CAL de un programa WHILE siempre es inyectiva?	No. Un programa puede terminar en la misma configuración ante entradas distintas.
¿La función CAL de un programa WHILE siempre es biyectiva?	No. Puesto que puede no ser ni inyectiva ni sobreyectiva.
Demostrar constructivamente que la función signo es WHILE-computable, siendo signo : N → N, donde signo(m) = 0, si m=0 y signo(m) = 1, si m>0.	Sea el programa WHILE Q = (1, 2, s) con s: while X1 ≠ 0 do X2 := X2 + 1; X1 := 0 od; X1 := X2 FQ = signo
¿La complejidad temporal de un programa WHILE es siempre una función total?	No. La función complejidad temporal no es una función total cuando la función calculada no es total.
¿Si Q es un programa WHILE y TQ su función complejidad temporal entonces TQ∈F(WHILE) ?	Sí. La función complejidad temporal puede ser parcial pero siempre es computable.
Demostrar constructivamente que la función complemento del signo es WHILEcomputable, siendo csigno : N → N, donde csigno(m) = 1, si m=0 y csigno(m) = 0, si m>0.	Sea el programa WHILE Q = (1, 2, s) con s: X2 := X2 + 1; while X1 ≠ 0 do X2 := 0; X1 := 0 od; X1 := X2 FQ = csigno
¿La función T de un programa WHILE siempre es sobreyectiva?	No. Puede suceder que para un programa y un número de pasos concreto, no exista ninguna entrada que haga que dicho programa acabe en ese número de pasos.
¿La función T de un programa WHILE siempre es inyectiva?	No. Un programa puede terminar en el mismo número de pasos ante entradas distintas.
Demostrar constructivamente que la función máximo es WHILE-computable, siendo maximo : N2 → N, donde maximo(n, m) = n, si n>m y maximo(n, m)= m, en otro caso.	Sea el programaWHILE Q = (2, 3, s) con s: X3 := X2 ; while X2 ≠ 0 do X1 := X1 – 1; X2 := X2 – 1 od; while X3 ≠ 0 do X1 := X1 + 1; X3 := X3 – 1 od FQ = maximo
¿La función T de un programa WHILE siempre es biyectiva?	No. Puesto que puede no ser ni inyectiva ni sobreyectiva.
Demostrar constructivamente que la función un cero es WHILE-computable, siendo uncero : N → N, donde uncero(n) = 0, si n=0 y no esta definida en otro caso.	Sea el programa WHILE Q = (1, 1, s) con s: while X1 ≠ 0 do X1 := X1 + 1 od FQ = uncero
¿Si Q es un programa WHILE entonces FQ diverge si y sólo si TQ diverge?	Sí. Dado que la función complejidad temporal nos indica en cuantos pasos acaba el programa, si ella es total la función calculada también, y si ella diverge para algún valor, para ese valor la función calculada también diverge.
¿Si un programa WHILE pasa dos veces por la misma configuración, entonces no acaba?	Sí. Es indicativo de que ha entrado en un bucle, que se repetirá indefinidamente.
Demostrar constructivamente que la función diverge es WHILE-computable, siendo diverge : N → N, donde diverge no está definida.	Sea el programa WHILE Q = (1, 1, s) con s: X1 := X1 + 1; while X1 ≠ 0 do X1 := X1 + 1 od FQ = diverge
¿Puede un programa WHILE diverger sin pasar dos veces por la misma configuración?	Sí. Puesto que el contenido de las variables no está acotado.
¿Si f es WHILE-calculable entonces f no diverge?	No. La función f puede ser parcial y computable.
¿ suma(producto,resta) ∈ T–WHILE ?	Sí. La composición de funciones totales siempre es total.
¿Todos los predicados asociados a funciones WHILE-computables son decidibles?	No. Son enumerables. Para que sean decidibles además la función ha de ser total.
¿ T_WHILE = TREC ?	Sí. Ambos conjuntos están formados por todas las funciones computables totales.
¿ ∀Q∈WHILE, TQ∈TREC ?	No. La función complejidad temporal no pertenece a TREC cuando la función calculada no es total.
¿ ∃f∈TREC \| f∉F(WHILE) ?	No. Dado que toda función recursiva también es WHILE-calculable.
¿La estructura de control if–then–else–fi permite definir funciones no representables en WHILE?	No. F(WHILE_A) = F(WHILE) .
¿Si Q es un programa WHILE que no acaba para alguna entrada entonces se cumple que FQ ∈ (REC – TREC) ?	Sí. Por la definición de función parcial y el teorema de equivalencia.
¿Toda función total WHILE-computable pertenece a TREC?	Sí. Por la definición de función total y el teorema de equivalencia.
¿ \|\| ( F(WHILE) – TREC ) \|\| ≥ ℵ0 ?	Sí. Concretamente es igual, ya que el conjunto F(WHILE) es infinito numerable, y cualquier subconjunto infinito de un conjunto numerable es infinito numerable..
¿ INI ⊆ T_WHILE ?	Sí. Las funciones INI son computables y totales.
Si una MT tiene k estados y n símbolos en su alfabeto, entonces el número de filas de su tabla es:	k*(n+1)
¿Una configuración de una MT es una dupla, una terna o una aplicación?	Una terna
¿Si las funciones suma y resta son las habituales para naturales, entonces:μ[suma] = μ[π2,1 arriba 2 abajo 1]?	Sí.
¿Una función recursiva f calculada como composición de funciones recursivas, tiene un número de argumentos igual al número de funciones internas de la composición?	No, es igual al número de argumentos de las funciones internas de la composición.
Si f = μ[suma], entonces: ¿f= μ[resta]?	No. f = μ[π2,1]
¿Una función recursiva f calculada como composición de funciones recursivas, tiene un número de argumentos igual al número de argumentos de las funciones internas de la composición?	Sí
¿Cuántas filas tiene una MT con tres estados y dos símbolos?	Nueve filas.
¿Si f = μ[resta]. entonces f = μ[suma]?	No, f = μ[π1,1]
Dada una función recursiva cualquiera, ¿la función es Turing-decidible?	No. La función es WHILE-computable.
Dada una función recursiva cualquiera, ¿la función es WHILE-computable?	Sí.
¿Una función recursiva es siempre parcial si para su definición se utiliza el operador de minimización no acotada?	No siempre, puede ser parcial si se cumple las condiciones, pero no tiene por qué.
En una MT si una configuración transita directamente a otra no terminal, entonces ¿dichas configuraciones pueden ser iguales?	Sí, dichas configuraciones pueden ser iguales aunque la segunda no sea terminal.
¿Una función recursiva f definida mediante el operador de minimización no acotada es una función parcial en cualquier caso?	No, puede ser una función total.
Sea Q = (2,2,S) con s: While X2 != 0 do: x1 := x1 +1; x2 := x2-1; od ¿Qué función representa para fq(n.m)?	Fq(n,m) = n+m para todo n,m natural
¿Si una función es total y tiene cero argumentos, entonces también es parcial?	FALSO. Una función total puede tener cero argumentos sin ser parcial.
¿Si una función es total ha de tener al menos un argumento?	FALSO. Una función total puede tener cero argumentos sin ser parcial.
¿Una función total puede tener cero argumentos sin ser parcial?	VERDADERO.
Sea Q = (2,2,S) con s: While X2 != 0 do: x1 := x1 +1; x2 := x2-1; od Desde la configuración (1,0,1) es posible transitar a:	(2,0,1)
Si para una MT de varios estados hay computaciones terminadas pero no hay computaciones completas, entonces ¿podemos afirmar que no computa ninguna función?	Sí.
Si para una MT de varios estados hay computaciones terminadas pero no hay computaciones completas, entonces ¿podemos afirmar que podemos hacer una MT con menos estados que compute la misma función?	No, porque no computa ninguna función.
Si para una MT de varios estados hay computaciones terminadas pero no hay computaciones completas, entonces ¿podemos afirmar que la función computada es de cero argumentos?	No, porque no computa ninguna función.
En una composición, ¿siempre hay más funciones internas que externas?	No, el número puede coincidir.
En una composición, ¿siempre hay más funciones externas que internas?	No, el número puede coincidir.
Sea Q perteneciente a while con Q = (n,p,s) y c = (m,x) una configuración de Q. Diremos que c es una configuración ninicial de Q sii:	m = 1 y xn+1 = xp = 0
Un predicado es Turing-decidible si:	es el predicado asociado a una función total Turing computable
Sea la función recursiva f = σ(<Θ \| π2,2>), ¿cual sería su definición?	f: N -> N, f(x) = 1
En una MT con un único estado y la cinta vacía, ¿el conjunto de configuraciones que son a la vez iniciales y terminales puede ser infinito?	Sí.
En una MT con un único estado y la cinta vacía, ¿el conjunto de configuraciones que son a la vez iniciales y terminales puede ser vacío?	No.
Si f = μ[g] entonces ¿puede tener g cero argumentos?	No, nunca.
Si un programa WHILE de tamaño 6 transita directamente de (5,1,1) a (2,1,1) ¿contiene bucles?	Obviamente.
¿El conjunto de configuraciones de una MT puede ser finito o infinito dependiendo de la MT?	No. Siempre es infinito.
Si en la tercera columna de una MT hay elementos repetidos, ¿cuántos estados tiene?	Tiene menos de tres estados.
Una función f es WHILE-computable si y sólo si	existe un programa WHILE Q \| FQ = f
¿Se puede calcular siempre la complejidad temporal?	No, no puede calcularse cuando no es posible alcanzar una configuración terminal.
¿Una tabla de una MT puede tener sólo una fila?	No.
¿Que representa la tercera columna de una tabla de una MT?	La función de instrucción
Si un conjunto es vacío, ¿cuánto vale su función característica?	Siempre vale cero.
En una recursión primitiva, ¿la función base tiene siempre los mismos argumentos que la función de inducción?	No, la función base tiene dos argumentos menos que la función de inducción.
"Principia Mathematica" fue escrito por:	Alfred N. Whitehead y Bertrand Russell
El teorema de incompletitud de K.Gödel se publicó	Antes de 1936
¿TREC es un subconjunto de las funciones iniciales?	No, TREC incluye a las funciones iniciales.

Descubre

Crear Tarjetas

Acerca de Nosotros

Explore Tarjetas

Comparta este Set de Tarjetas de Aprendizaje

Tarjetas de Aprendizaje relacionadas

Talf Bloque 3

Cómo estudiar sus tarjetas

Rango de Cartas a estudiar

192 Cartas en este set