Test B3

Si una MT tiene k estados y n símbolos en su alfabeto, entonces el número de filas de su tabla es: n*(k+1). n*k. k*(n+1).

Una configuración de una MT es: un par. una terna. una aplicación.

Sea el programa WHILE Q (1, 2, s) donde s es el siguiente código WHILE: X2 := X1 - 1; While X2 != 0 do X1 := producto (X1,X2); X2 :- X2 -1 od La línea X1 := producto (X1,X2) es una macroinstrucción (lenguaje WHILE ampliado) y se tratará como una única instrucción ¿Cuánto vale Tq(n)?. 4(n-1)+2. 4n+2. 4(n-1)+1.

¿Cuál de las siguientes expresiones es la definición de la función constante de dos argumentos de devuelve uno?. σ(< Θ|π1,1 | π3,3>). σ(<Θ|π2,2>). σ(<<Θ|π2,2> | π3,3>).

Si las funciones suma y resta son las habituales para naturales, entonces: μ[suma]=μ[resta]. μ[suma]=μ[π2,1]. suma = < π2,1 | σ(π2,2)>.

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 la función externa de la composición. igual al número de argumentos de las funciones internas de la composición. igual al número de funciones internas de la composición.

Si f = μ[suma], entonces. f = μ[resta]. f = μ[π2,1]. f = μ[π2,2].

La tabla de una MT con tres estados y dos símbolos tiene: seis filas, o menos. nueve filas. cinco columnas.

Para la MT dada por la tabla: 0 * L 1 0 | L 1 1 * h 1 1 | L 1. existe sólo una configuración inicial para la cual la MT no se para. existe más de una configuración inicial para las cuales la MT no se para. no existe ninguna configuración inicial para la cual la MT no se para.

Sea el programa WHILE Q (1, 2, s) donde s es el siguiente código WHILE: X2 := X1 - 1; While X2 != 0 do X1 := producto (X1,X2); X2 :- X2 -1 od La línea X1 := producto (X1,X2) es una macroinstrucción (lenguaje WHILE ampliado) y se tratará como una única instrucción ¿Cuál de las siguientes es una computación completa de Q?. (1,2,0) |- (2,2,1) |- (3,2,0) |- (4,2,0) |- (5,2,0) |- (2,2,0) |- (6,2,0). (1,2,0) |- (2,2,1) |- (3,2,1) |- (4,2,1) |- (5,2,0) |- (2,2,0) |- (6,2,0). (0,2,0) |- (1,2,1) |- (2,2,1) |- (3,2,1) |- (5,2,0) |- (2,2,0) |- (6,2,0).

Si f = μ[resta], entonces. f - μ[producto]. f = μ[suma]. f = π1,1.

¿Cuál de las siguientes es una función recursiva?. <π1,1 | σ(π3,3)> (π2,2 , π2,1). <π1,1 | σ(π3,3)> (π1,2 , π2,1). <π1,1 | σ(π3,3)> (π2,2).

Dada una función recursiva cualquiera, se cumple que: la función es Turing - decidible. la función es While - computable. existe una MT que la representa y que para cualquier configuración inicial se detiene en un número finito de pasos.

Una función recursiva: no puede ser parcial. puede ser parcial para su definición se utiliza el operador de minimización no acotada. es parcial si para su definición se utiliza el operador de minimización no acotada.

En una MT si una configuración transita directamente a otra entonces: dichas configuraciones pueden ser iguales aunque la segunda no sea terminal. dichas configuraciones son distintas. dichas configuraciones pueden ser iguales sólo si la segunda es terminal.

Una función recursiva f definida mediante el operador de minimización no acotada (f = μ[g]): es una función parcial sólo si la función auxiliar g es también parcial. puede ser una función total. es una función parcial en cualquier caso.

Sea Q = (2,2) con s: While X2 != 0 do X1 := X1 + 1; X2 := X2 -1 od. Fq (n,m) = n*m ∀n,m ∈ N. Fq (n,m) = n+m ∀n,m ∈ N. Fq (n,m) = 2n ∀n ∈ N.

Marca la afirmación verdadera. Si una función es total ha de tener al menos un argumento. Si una función es total y tiene cero argumentos, entonces también es parcial. Una función total puede tener cero argumentos sin ser parcial.

Dado Q (2,2,s) con s: While X2 != 0 do X1 := X1 + 1; X2 := X2 - 1 od. (5,0,1). (2,0,1). (2,0,2).

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. que no computa ninguna función. que la función computada es de cero argumentos.

En una composición. siempre hay más funciones internas que externas. siempre hay más funciones externas que internas. el número de funciones internas y externas puede coincidir.

Sea Q ∈ WHILE con Q = (n, p, s), y sea c= (m,x) una configuración de Q. Diremos que c es una configuración inicial de Q sii: m = 0 y Xn+1 = ... = Xp = 0. m = 1 y Xn+1 = ... = Xp = 0. m = 1 y X1 = ... = Xp = 0.

Un predicado es Turing-decidible si: es el predicado asociado a una función Turing computable. es el predicado a una función parcial Turing computable. es el predicado asociado a una función total Turing computable.

Sea la función recursiva f = σ(<Θ |π2,2>). f: N -> N, f(x) = 1. f: N -> N, f(x) = 2. f: N^2 -> N, f(x,y) = 1.

En una MT si una configuración transita directamente a otra entonces: dichas configuraciones son distintas. dichas configuraciones pueden ser iguales aunque la segunda no sea terminal. dichas configuraciones pueden ser iguales sólo si la segunda es terminal.

Una configuración de una MT es: una aplicación. una terna. un par.

(q3,...**11011*_...). (q3,...**11011_*...). (q3,...**110*_**...).

En una MT con un único estado y la cinta vacía, el conjunto de configuraciones que son a la vez iniciales y terminales: no puede ser ni vacio ni infinito. puede ser infinito. es vacío.

Sea la función recursiva f = σ(μ[g]), con g = <π1,1| σ(π3,3)> entonces: f(0) = 0. f(1) = ↑. f(1) = 0.

Si f = μ[g], entonces: g ha de tener como máximo dos argumentos. g no puede tener cero argumentos. g ha de tener como mínimo dos argumentos.

(1+0)*101. 101(1+0)*. (1+0)*101(1+0)*.

Sea Q = (2,2,s) con s: While X2 != 0 do X1 := X1 + 1; X2 : = X2 -1 od. CALq (2,0,3) = (4,0,3). CALq (2,0,3) = (5,2,0). CALq (5,1) = (6,2).

(4, ... * |||| *_ ...). (0,...*|||*_...). (4, ... * ||| *_ ...).

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

El conjunto de configuraciones de una MT. siempre es infinito. puede ser finito o infinito dependiendo de la MT. siempre es finito.

CALq(5,4) = (5,3,4). CALq(5,4) = (5,4,4). CALq(5,4) = (5,4,5).

f(3,1)=4. f(3,1)=2. f(3,1)=0.

En una tabla de una MT. si en la tercera columna hay elementos repetidos entonces tiene más de dos estados. en la tercera columna siempre hay elementos repetidos. si en la tercera columna no hay elementos repetidos entonces tiene menos de tres estados.

Una MT puede ejecutar el siguiente método de operación ...*w* -> ...*ww*... en menos de 100 pasos de cómputo. sólo si se ejecuta la instrucción halt. con menos de 10*|w| estados.

CALq(5,5) = (6,3,5). CALq(5,5) = (6,4,5). CALq(5,5) = (5,4,4).

Tq(n) = 3n + 3 ∀n∈N. Tq(n) = 2n + 2 ∀n∈N. Tq(n) = 4n + 2 ∀n∈N.

Una función f es WHILE-computable si y sólo si. existe un programa WHILE Q |Fq = f. puede representarse como la composición de funciones iniciales. existe un programa WHILE Q | Tq es total.

f(2) = 1. f(2) = 0. f(2) = 2.

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 X1 al final del proceso de cómputo, siempre que se alcance una configuración terminal. es una función total.

f(3,2) = 1. f(3,2) = 5. f(3,2) = 6.

La expresión de cinta de una MT es una aplicación que. siempre es biyectiva. nunca es biyectiva. a veces puede ser biyectiva y otras veces no.

Si f = μ[g] entonces. f tiene al menos un argumento. si f no es total, tampoco lo es g. g tiene al menos un argumento.

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

Una tabla de una MT. siempre tiene un número par de filas. no puede tener sólo una fila. no puede tener sólo dos filas.

La función recursiva <Θ | π2,1> es la función. constante cero de dos argumentos. máximo {n-1,0}, donde n es el argumento de la función. constante cero de un argumento.

La tercera columna de una tabla de una MT representa. la función de instrucción. la función parada. la función de transición.

Si un conjunto es vacío su función característica. siempre vale cero. siempre vale uno. no existe.

En una recursión primitiva. la función base tiene dos argumentos menos que la función de inducción. la función base tiene los mismos argumentos que la función de inducción. la función base tiene un argumento menos que la función de inducción.

En una composición. el número de funciones internas y externas puede coincidir. siempre hay más funciones internas que externas. siempre hay más funciones externas que internas.

"Principia Mathematica" fue escrito por. Alan M.Turing. Alfred N. Whitehead y Bertrand Russel. Stephen C. Kleene y Alonzo Church.

El teorema de incompletitud de K.Gödel se publicó. después de 1963. antes de 1963. en 1963.

El concepto de sistema de numeración es. posterior a la aparición del cero. simultáneo a la aparición del cero. anterior a la aparición del cero.

f(4,2) = 6. f(4,2) = 2. f(4,2) = 1.

Una MT de un estado sobre una cinta no vacía. puede parar sobre el cuadrado escrutado inicial. para con cualquier contenido de la cinta. nunca se para.

¿Cuál de las siguientes afirmaciones es cierta?. Si un conjunto es WHILE-enumerable entonces debe ser WHILE-decidible. Toda función WHILE-computable es total. si f∈ T - WHILE -> Pf ∈ PRED(WHILE).

Una función while-calculable es aquella que se puede representar mediante. al menos, un programa while. un programa que sólo contiene instrucciones de asignación. un programa que contiene uno o más bucles indefinidos.

¿Cuál de estas MT rrealiza el cálculo ...*1_w*... -> *1w*_...,si w ∈ {1}*?. (q0 * r 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).

no está definida para ningún valor del dominio. está definida para un ocnjunto finito de valores del dominio. es total.

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

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

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

Una MT realiza la transición (q2, ...*10_1*...,7) |- (q5,...*101_*...,8), porque su tabla contiene la línea. (q5 1 r q2). (q2 1 l q5). (q2 0 r q5).

12. 15. 17.

parará solamente en un símbolo del alfabetp. se para sobre un cuadrado de la expresión de cinta. podría parar o no parar, según las cadenas de la expresión de cinta.

Fq() = ↑. Fq () = 0. Fq = () = 1.

Pf es un predicado recursivamente decidible. negado(Pf(x)), ∀x !=0. El conjunto de valores de verdad es Vpf = ∅.