Diferencia entre revisiones de «Final del 21/10/14 (Lógica y Computabilidad)»
Sin resumen de edición |
Sin resumen de edición |
||
| Línea 4: | Línea 4: | ||
Hay que probar la existencia y la unicidad de que existe una única valuación que extiende a la función f. | Hay que probar la existencia y la unicidad de que existe una única valuación que extiende a la función f. | ||
*La existencia se prueba por inducción en la complejidad de la fórmula definiendo en cada caso cómo se evalúa. | *La existencia se prueba por inducción en la complejidad de la fórmula definiendo en cada caso cómo se evalúa. | ||
Caso Base: sea a tal que comp(a) = 0, entonces a es una variable proposicional. Entonces f(a) está definida. Por lo tanto v(a) = f(a). | Caso Base: sea a tal que comp(a) = 0, entonces a es una variable proposicional. Entonces f(a) está definida. Por lo tanto v(a) = f(a). | ||
Paso Inductivo: supongamos válido hasta n, siendo n igual a la complejidad de a. Veamos si comp(a) = n + 1. | Paso Inductivo: supongamos válido hasta n, siendo n igual a la complejidad de a. Veamos si comp(a) = n + 1. | ||
- Si a = ¬b, entonces comp(b) = n, por lo que por H.I. v(b) está definido. Queda que v(a) = 1 - v(b) | - Si a = ¬b, entonces comp(b) = n, por lo que por H.I. v(b) está definido. Queda que v(a) = 1 - v(b) | ||
- Si a = b * c, con * siendo conector AND, OR o ->. Entonces comp(b) y comp(c) son menores a n+1. Por H.I. v(b) y v(c) están definidos. Por lo tanto: | - Si a = b * c, con * siendo conector AND, OR o ->. Entonces comp(b) y comp(c) son menores a n+1. Por H.I. v(b) y v(c) están definidos. Por lo tanto: | ||
v(a) = mín(v(b),v(c)) si a = b AND c | v(a) = mín(v(b),v(c)) si a = b AND c | ||
v(a) = máx(v(b),v(c)) si a = b OR c | v(a) = máx(v(b),v(c)) si a = b OR c | ||
v(a) = máx(1 - v(b),v(c)) si a = b -> c | v(a) = máx(1 - v(b),v(c)) si a = b -> c | ||
La función v queda definido para toda fórmula de cualquier complejidad. | La función v queda definido para toda fórmula de cualquier complejidad. | ||
* La unicidad se prueba suponiendo que existiese otra función de valuación w que extiende a f | * La unicidad se prueba suponiendo que existiese otra función de valuación w que extiende a f | ||
Consideremos el siguiente conjunto: | Consideremos el siguiente conjunto: | ||
I = {a | |||
<math>I = \{ a \in Form \quad \mid \quad v(a) = w(a)\}</math> | |||
Como w también extiende a f, I contiene a todas las variables proposicionales. Y como v y w son ambas valuaciones, I es cerrado por los conectivos por lo que Form está incluido en I. Es decir, v(P) = w(P) para toda fórmula P. | Como w también extiende a f, I contiene a todas las variables proposicionales. Y como v y w son ambas valuaciones, I es cerrado por los conectivos por lo que Form está incluido en I. Es decir, v(P) = w(P) para toda fórmula P. | ||
Usa el teorema de que si subconjunto S de A* es cerrado por los conectivos u S contiene a todas las variables proposicionales entonces S contiene a todas las fórmulas. | Usa el teorema de que si subconjunto S de A* es cerrado por los conectivos u S contiene a todas las variables proposicionales entonces S contiene a todas las fórmulas. | ||
Unicidad basado en el apunte de lógica de Roberto Cignoli y Guillermo Martínez. Según Alejandro Petrovich también salía por inducción en la complejidad de la fórmula. | Unicidad basado en el apunte de lógica de Roberto Cignoli y Guillermo Martínez. Según Alejandro Petrovich también salía por inducción en la complejidad de la fórmula. | ||
=Ejercicio 2= | =Ejercicio 2= | ||
a) La interpretación de un lenguaje de primer orden es una extensión del lenguaje que mapea cada símbolo constante, función k-aria y predicado k-ario a algún elemento del universo de interpretación. | a) La interpretación de un lenguaje de primer orden es una extensión del lenguaje que mapea cada símbolo constante, función k-aria y predicado k-ario a algún elemento del universo de interpretación. | ||
Sea L=<C,F,P>, para una interpretación se define: | Sea L=<C,F,P>, para una interpretación se define: | ||
- Un universo de interpretación, conjunto no nulo <math>U_I</math>. Ejemplo: Naturales. | - Un universo de interpretación, conjunto no nulo <math>U_I</math>. Ejemplo: Naturales. | ||
- Para cada símbolo de constante c <math>\in</math> C, mapea con un elemento <math>c_I \in U_I</math>. Ejemplo "cero" -> <math>c_i = 0</math> | - Para cada símbolo de constante c <math>\in</math> C, mapea con un elemento <math>c_I \in U_I</math>. Ejemplo "cero" -> <math>c_i = 0</math> | ||
- Para cada símbolo de función k-aria <math>\in</math> F, mapea con una función <math>f_I</math> de k variables sobre el universo <math>U_I: f_I: U^{k}_{I} -> U_I</math> | - Para cada símbolo de función k-aria <math>\in</math> F, mapea con una función <math>f_I</math> de k variables sobre el universo <math>U_I: f_I: U^{k}_{I} -> U_I</math> | ||
- Para cada símbolo de predicado k-ario <math>\in</math> P, mapea a una relación k-aria <math>P_I</math> sobre el universo <math>U_I</math>. Osea: <math>U^{k}_{I} = U_I x ... x U_I</math> k veces. | - Para cada símbolo de predicado k-ario <math>\in</math> P, mapea a una relación k-aria <math>P_I</math> sobre el universo <math>U_I</math>. Osea: <math>U^{k}_{I} = U_I x ... x U_I</math> k veces. | ||
b) | b) | ||
| Línea 55: | Línea 76: | ||
<math>b = \forall x \forall y \forall z (f^2(x,f^2(y,z)) = f^2(f^2(x,y),z))</math> | <math>b = \forall x \forall y \forall z (f^2(x,f^2(y,z)) = f^2(f^2(x,y),z))</math> | ||
Solución: <math>a \wedge b</math> | Solución: <math>a \wedge b</math> | ||
| Línea 60: | Línea 82: | ||
=Ejercicio 3= | =Ejercicio 3= | ||
Una función es primitiva recursiva si se obtiene a través de las funciones iniciales por composición y/o recursión en finitos pasos. | |||
Sea <math>f:\mathbb{N}^2 \to \mathbb{N}</math> tal que <math>f(a,b)</math> devuelve la cantidad de divisores positivos desde <math>0</math> hasta <math>b</math>. Con <math>a</math> y <math>b</math> naturales. | Sea <math>f:\mathbb{N}^2 \to \mathbb{N}</math> tal que <math>f(a,b)</math> devuelve la cantidad de divisores positivos desde <math>0</math> hasta <math>b</math>. Con <math>a</math> y <math>b</math> naturales. | ||
Queremos que <math>\tau(n) = f(n,n) \forall n \in \mathbb{N}</math> definiendo a <math>f</math> de la siguiente forma: | Queremos que <math>\tau(n) = f(n,n) \forall n \in \mathbb{N}</math> definiendo a <math>f</math> de la siguiente forma: | ||
<math>f(n,0) = n(n)</math> | <math>f(n,0) = n(n)</math> | ||
| Línea 70: | Línea 96: | ||
Con <math>g(a,b,c) = \left\{ \begin{matrix} suc(u^3_3(a,b,c)) \quad si \quad P \\ u^3_3(a,b,c) \quad si \quad \neg P \end{matrix}</math> | Con <math>g(a,b,c) = \left\{ \begin{matrix} suc(u^3_3(a,b,c)) \quad si \quad P \\ u^3_3(a,b,c) \quad si \quad \quad \neg P \end{matrix}</math> | ||
donde <math>P = u^3_1(a,b,c) \mid u^3_2(a,b,c)</math> | donde <math>P = u^3_1(a,b,c) \quad \mid \quad suc(u^3_2(a,b,c))</math> | ||
<math>f</math> cumple con el esquema de recursión primitivo. | <math>f</math> cumple con el esquema de recursión primitivo. | ||
<math>n(n)</math> es la función inicial nula aplicada a <math>n</math> | <math>n(n)</math> es la función inicial nula aplicada a <math>n</math> | ||
El predicado <math>P</math> usa la función proyección y la función "divide a" (<math>\mid</math>) que es primitiva recursiva. | |||
La función <math>g</math> es una división de casos disjuntos y usa las funciones iniciales de proyección y sucesor. | |||
Por todo lo anterior, la función <math>f(n,m)</math> es primitiva recursiva (con <math>n</math> y <math>m</math> naturales) | |||
Falta ver que <math>\tau (n) = f(n,n)</math>. Probamos por inducción en el segundo parámetro. | |||
*Caso base: | |||
<math>\tau(0) = 0</math> | |||
<math>f(0,0) = n(0) = 0</math> | |||
*Paso inductivo. Se cumple la hipótesis inductiva f(n,m) devuelve los divisiores de n desde 0 hasta m. Ahora queremos ver para m+1: | |||
<math>f(n,m+1) = g(n,m,f(n,m))</math> | |||
Dos casos: | |||
- <math>n \mid (m+1)</math>: <math>g(n,m,f(n,m)) = f(n,m) + 1</math>. Entonces por H.I. al dividir m+1 incremento en 1 a lo ya calculado en el paso recursivo anterior y éste calculo correctamente hasta m. Queda <math>f(n,m+1) = f(n,m) + 1</math> | |||
- <math>\neg (n \mid (m+1))</math>: <math>g(n,m,f(n,m)) = f(n,m)</math>. Entonces por H.I. al no dividir m+1 no sumo nada a lo ya calculado en el paso recursivo anterior y éste calcula correctamente hasta m. Queda <math>f(n,m+1) = f(n,m)</math> | |||
Por lo tanto, <math>\tau(n) = f(n,n) \forall n \in \mathbb{N}</math> | |||
=Ejercicio 4= | |||
Sea: | |||
<math>f(x) = \{\begin{matrix} Halt(x,x) \quad \quad x \neq 0 \\ 2 \quad \quad \quad x = 0\end{matrix}</math> | |||
La <math>Img(f) = \{ 0,1,2 \}</math>. Tiene exactamente 3 elementos. | |||
Supongamos que <math>f(x)</math> es computable, entonces <math>\exists P \quad </math> programa que computa <math>f(x)</math>. | |||
Si <math>f(x) = 2</math>, entonces <math>x = 0</math>. | |||
Si <math>f(x) = 0 \quad o \quad f(x) = 1 \quad \longleftrightarrow \quad \psi_p(x) \downarrow \quad \rightarrow \quad Halt(x,x) \quad \vee \quad \neg Halt(x,x)</math> | |||
Caso particular, sea <math>e=#P</math>, <math>Halt(e,e)</math> determina si el programa <math>e</math> con entrada <math>e</math> termina o no. | |||
Como vimos en las teóricas, estamos resolviendo el ''halting problem''. | |||
Absurdo! pues ''Halt'' no es computable. Vino de suponer que <math>f(x)</math> era computable. | |||
Entonces <math>f(x)</math> no computable. | |||
Revisión del 16:36 22 oct 2014
Ejercicio 1
Hay que probar la existencia y la unicidad de que existe una única valuación que extiende a la función f.
- La existencia se prueba por inducción en la complejidad de la fórmula definiendo en cada caso cómo se evalúa.
Caso Base: sea a tal que comp(a) = 0, entonces a es una variable proposicional. Entonces f(a) está definida. Por lo tanto v(a) = f(a).
Paso Inductivo: supongamos válido hasta n, siendo n igual a la complejidad de a. Veamos si comp(a) = n + 1.
- Si a = ¬b, entonces comp(b) = n, por lo que por H.I. v(b) está definido. Queda que v(a) = 1 - v(b)
- Si a = b * c, con * siendo conector AND, OR o ->. Entonces comp(b) y comp(c) son menores a n+1. Por H.I. v(b) y v(c) están definidos. Por lo tanto:
v(a) = mín(v(b),v(c)) si a = b AND c
v(a) = máx(v(b),v(c)) si a = b OR c
v(a) = máx(1 - v(b),v(c)) si a = b -> c
La función v queda definido para toda fórmula de cualquier complejidad.
- La unicidad se prueba suponiendo que existiese otra función de valuación w que extiende a f
Consideremos el siguiente conjunto:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle I = \{ a \in Form \quad \mid \quad v(a) = w(a)\}}
Como w también extiende a f, I contiene a todas las variables proposicionales. Y como v y w son ambas valuaciones, I es cerrado por los conectivos por lo que Form está incluido en I. Es decir, v(P) = w(P) para toda fórmula P.
Usa el teorema de que si subconjunto S de A* es cerrado por los conectivos u S contiene a todas las variables proposicionales entonces S contiene a todas las fórmulas.
Unicidad basado en el apunte de lógica de Roberto Cignoli y Guillermo Martínez. Según Alejandro Petrovich también salía por inducción en la complejidad de la fórmula.
Ejercicio 2
a) La interpretación de un lenguaje de primer orden es una extensión del lenguaje que mapea cada símbolo constante, función k-aria y predicado k-ario a algún elemento del universo de interpretación.
Sea L=<C,F,P>, para una interpretación se define:
- Un universo de interpretación, conjunto no nulo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U_I}
. Ejemplo: Naturales.
- Para cada símbolo de constante c Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in} C, mapea con un elemento Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_I \in U_I} . Ejemplo "cero" -> Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_i = 0}
- Para cada símbolo de función k-aria Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in} F, mapea con una función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_I} de k variables sobre el universo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U_I: f_I: U^{k}_{I} -> U_I}
- Para cada símbolo de predicado k-ario Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in} P, mapea a una relación k-aria Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P_I} sobre el universo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U_I} . Osea: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U^{k}_{I} = U_I x ... x U_I} k veces.
b)
- Conmutativo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a = \forall x \forall y (f^2(x,y) = f^2(y,x))}
- Asociativo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle b = \forall x \forall y \forall z (f^2(x,f^2(y,z)) = f^2(f^2(x,y),z))}
Solución: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a \wedge b}
Ejercicio 3
Una función es primitiva recursiva si se obtiene a través de las funciones iniciales por composición y/o recursión en finitos pasos.
Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f:\mathbb{N}^2 \to \mathbb{N}} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(a,b)} devuelve la cantidad de divisores positivos desde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 0} hasta Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle b} . Con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle b} naturales.
Queremos que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \tau(n) = f(n,n) \forall n \in \mathbb{N}}
definiendo a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f}
de la siguiente forma:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,0) = n(n)}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m+1) = g(n,m,f(n,m))}
Con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(a,b,c) = \left\{ \begin{matrix} suc(u^3_3(a,b,c)) \quad si \quad P \\ u^3_3(a,b,c) \quad si \quad \quad \neg P \end{matrix}}
donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P = u^3_1(a,b,c) \quad \mid \quad suc(u^3_2(a,b,c))}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f}
cumple con el esquema de recursión primitivo.
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n(n)} es la función inicial nula aplicada a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n}
El predicado Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P} usa la función proyección y la función "divide a" (Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mid} ) que es primitiva recursiva.
La función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g} es una división de casos disjuntos y usa las funciones iniciales de proyección y sucesor.
Por todo lo anterior, la función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m)} es primitiva recursiva (con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle m} naturales)
Falta ver que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \tau (n) = f(n,n)}
. Probamos por inducción en el segundo parámetro.
- Caso base:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \tau(0) = 0}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(0,0) = n(0) = 0}
- Paso inductivo. Se cumple la hipótesis inductiva f(n,m) devuelve los divisiores de n desde 0 hasta m. Ahora queremos ver para m+1:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m+1) = g(n,m,f(n,m))}
Dos casos:
- Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n \mid (m+1)} : Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(n,m,f(n,m)) = f(n,m) + 1} . Entonces por H.I. al dividir m+1 incremento en 1 a lo ya calculado en el paso recursivo anterior y éste calculo correctamente hasta m. Queda Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m+1) = f(n,m) + 1}
- Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neg (n \mid (m+1))}
: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(n,m,f(n,m)) = f(n,m)}
. Entonces por H.I. al no dividir m+1 no sumo nada a lo ya calculado en el paso recursivo anterior y éste calcula correctamente hasta m. Queda Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m+1) = f(n,m)}
Por lo tanto, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \tau(n) = f(n,n) \forall n \in \mathbb{N}}
Ejercicio 4
Sea:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x) = \{\begin{matrix} Halt(x,x) \quad \quad x \neq 0 \\ 2 \quad \quad \quad x = 0\end{matrix}}
La Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Img(f) = \{ 0,1,2 \}}
. Tiene exactamente 3 elementos.
Supongamos que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x)}
es computable, entonces programa que computa .
Si , entonces .
Si
Caso particular, sea Error al representar (error de sintaxis): {\displaystyle e=#P}
, determina si el programa con entrada termina o no.
Como vimos en las teóricas, estamos resolviendo el halting problem.
Absurdo! pues Halt no es computable. Vino de suponer que era computable.
Entonces no computable.
