« Cuadernos del CIS: Si… « || Inicio || » TC: Programas y Funci… »

TC: Preliminares

Última modificación: 9 de Noviembre de 2017, y ha tenido 181 vistas

Etiquetas utilizadas: || || ||

Este capítulo está dedicado a introducir de forma muy somera los fundamentos de los conceptos y herramientas matemáticas que necesitaremos a lo largo del curso. Ha de tenerse en cuenta que un curso de Teoría de la Computabilidad de estas características es prácticamente autocontenido, pues todo se define desde la base, aunque son necesarios algunos conceptos habituales en matemáticas como los que aquí se presentan.

Conjuntos

Notaremos los conjuntos por letras mayúsculas: \(A,B,...,S,T\), y sus elementos por letras minúsculas: \(x,y,z,...\)

Cuando un elemento, \(x\), pertenezca a un conjunto, \(A\), notaremos: \(x \in A\), y si no pertenece, lo notaremos: \(x \notin A\).

Como conjuntos especiales, notaremos por \({\Bbb N}\) al conjunto de los número naturales (\({\Bbb N}=\{0,1,2,3,...\}\)), y por \(\emptyset\) al conjunto vacío (el que no tiene elementos).

Diremos que dos conjuntos, \(A,B\), son iguales, \(A=B\), cuando tengan los mismos elementos, y diremos que \(A\) es subconjunto de \(B\), \(A \subseteq B\) cuando todo elemento de \(A\) sea elemento de \(B\). Diremos que es un subconjunto propio, \(A \subset B\), cuando se verifique \(A\subseteq B\), pero \(A\neq B\).

$\begin{cases} A=B &: &\ \forall x\ (x\in A \Leftrightarrow x\in B)\\
A\subseteq B &: &\ \forall x\ (x\in A \Rightarrow x\in B)\end{cases}$

Esta es la base de las pruebas por doble inclusión:

\(A=B \Leftrightarrow (A\subseteq B \wedge B\subseteq A)\)

Podemos definir un conjunto por medio de las propiedades que verifican sus elementos, así:

$\begin{cases}A \cup B &=&\{x: x\in A \mbox{ ó } x\in B\}\\
A \cap B &=& \{x: x\in A \mbox{ y } x\in B\}\\
A - B &=& \{x: x \in A \mbox{ y } x \notin B\}\end{cases}$

Si \(A\subseteq C\), al conjunto \(C-A\) se le denomina complementario de \(A\) en \(C\). Habitualmente, cuando esté claro con qué conjunto \(C\) estemos trabajando (por ejemplo, si hablamos de números naturales) lo notaremos abreviadamente por \(\overline{A}\).

En estas condiciones, se verifican las leyes de De Morgan, si \(A,B\subseteq C\):

$\begin{cases}\overline{A\cup B} &=& \overline{A} \cap \overline{B}\\
\overline{A\cap B} &=& \overline{A} \cup \overline{B}\end{cases}$

Si \(A\) es un conjunto, definimos el conjunto partes de \(A\), \({\cal P}(A)\), como:

\({\cal P}(A)=\{B : B \subseteq A\}\)

Ejemplos:

  1. Sean \(A=\{1,2,3\},\ B=\{0,1,4\}\). Entonces:
    $$A\cup B=\{0,1,2,3,4\},\ A\cap B=\{1\},\ A-B=\{2,3\},\ B-A=\{0,4\}\\
    {\cal P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$$
  2. Sean \(P=\{x \in {\Bbb N}: x \mbox{ par}\},\ I=\{x \in {\Bbb N}: x \mbox{ impar }\}\). Entonces:
    $$P\cup I={\Bbb N},\ P\cap I=\emptyset,\ P-I=P,\ I-P=I,\ {\Bbb N}-P=I (\overline{P}=I)$$

Tuplas

Se define una \(n\)-tupla como una sucesión de \(n\) elementos, \((a_1,...,a_n)\). La propiedad fundamental que diferencia
una \(n\)-tupla de un conjunto finito es el papel que desempeña el orden entre sus elementos, así, dadas
\((a_1,...,a_n),(b_1,...,b_m)\):

\((a_1,...,a_n)=(b_1,...,b_m) \Leftrightarrow m=n \mbox{ y } a_1=b_1,...,a_n=b_n\)

A diferencia de los conjuntos unitarios (con un sólo elemento), que verifican \(a\neq \{a\}\), en las tuplas identificamos los objetos con las \(1\)-tuplas, así: \(a=(a)\)

Si \(A_1,...,A_n\) son conjuntos, definimos el producto cartesiano de \(A_1,...,A_n\) como el conjunto de \(n\)-tuplas siguiente:

\(A_1 \times ... \times A_n=\{(a_1,...,a_n): a_i \in A_i\ (1 \leq i \leq n)\}\)

Lo denotaremos por \(A^n=A\underbrace{\times ... \times}_{n \ veces} A\)

Ejemplos:

  1. \(A_1=\{1,2\},\ A_2=\{3,4\},\ A_3=\{5,6\}\)
    $$A_1\times A_2 \times A_3 = \{(1,3,5),(1,3,6),(1,4,5),(1,4,6), (2,3,5),(2,3,6),(2,4,5),(2,4,6)\}$$
  2. \(A=\{1,2\}\)
    $$A^3= \{(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)\}$$

Funciones

Definimos una función o aplicación, \(f\), entre dos conjuntos, \(A,B\), como un subconjunto de \(A\times B\) que verifica:

\((a,b_1),(a,b_2)\in f \Rightarrow b_1=b_2\)

Se escribirá \(f(a)=b\) para expresar que \((a,b)\in f\).

Dada una función \(f\) se definen el dominio y el rango de \(f\), respectivamente como los conjuntos:

$\begin{cases} dom(f)&=&\{a:\ \exists b\ (f(a)=b)\}\\
rang(f)&=&\{b:\ \exists a\ (f(a)=b)\}\end{cases}$

Si \(C\subseteq A, D\subseteq B\), notaremos:

$\begin{cases} f(C) &=& \{f(x): x \in C\}\\
f^{-1}(D) &=& \{x\in A: f(x)\in D\}\end{cases}$

Si \(f\) es una función entre \(A\) y \(B\), en general se tiene que \(dom(f)\subseteq A\), y se notará \(f:A {- \to} B\). Cuando \(dom(f)=A\) diremos que la función es total, y se escribirá \(f:A\to B\). En este caso, si \(a\in A-dom(f)\), escribiremos \(f(a)\uparrow\), y si \(a \in dom(f)\), \(f(a)\downarrow\).

Definición: Dadas \(f,g:A - \to B\), escribiremos \(f(x)\simeq g(x)\) para notar

\((f(x)\uparrow \wedge\ g(x)\uparrow)\ \vee\ (f(x)\downarrow \wedge\ g(x)\downarrow \wedge\ f(x)=g(x))\)

Algunos tipos especiales de funciones son:

  1. Inyectiva: \(f(x_1)=f(x_2) \Rightarrow x_1=x_2\) (esto es: \(x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)\))
  2. Sobreyectiva: \(rang(f)=B\), es decir, \(\forall y\in B\ \exists x\ (f(x)=y)\)
  3. Biyectiva: Si es inyectiva y sobreyectiva.

Si \(f:A \to B\), diremos que \(A\) es cerrado bajo \(f\) si \(rang(f)\subseteq A\).

En general, diremos que una función es \(n\)-aria cuando el conjunto de partida sea un producto cartesiano de \(n\) conjuntos. Es decir, \(f: A_1\times ...\times A_n \to B\), y normalmente se notará la acción sobre los puntos del conjunto de partida: \(f(a_1,...,a_n)\).

Definición: Si \(f:A \to B\), \(g:B \to C\) son dos aplicaciones, definimos la composición de \(f\) y \(g\), \(g\circ f: A \to C\), por: \((g\circ f)(x)=g(f(x))\).

Ejemplos:

  1. \(f:{\Bbb N} \to {\Bbb N}\), dada por \(f(n)=n^2\). Es total, inyectiva y no sobreyectiva. Además, \({\Bbb N}\) es cerrado bajo \(f\).
  2. \(f:{\Bbb N} \times {\Bbb N} \to {\Bbb N}\), dada por \(f(n,m)=m-n\ (m\geq n)\). Es parcial, no inyectiva y sobreyectiva.
  3. \(f:{\Bbb N} \to {\Bbb Q}\), dada por \(f(n)=\frac{n}{2}\). Es total, inyectiva, no sobreyectiva. Además, \({\Bbb N}\) no es cerrado bajo \(f\).

Predicados

Definición: Un predicado definido sobre un conjunto, \(A\), es una función total, \(P:A \to \{0,1\}\). Identificaremos el valor \(0\) como falso, y el \(1\) como verdadero, diciendo:

\(P(x) \mbox{ verdad, si } P(x)=1\)
\(P(x) \mbox{ falso, si } P(x)=0\)

Usualmente, los predicados se escriben como sentencias o propiedades, así: \((x<5)\) es el predicado que toma el valor de \(1\) si \(x<5\) y \(0\) en caso contrario.

Si \(P\) y \(Q\) son dos predicados, definimos:

\(P\) \(Q\) \(\neg P\) \(P\wedge Q\) \(P\vee Q\)
0 0 1 0 0
0 1 1 0 1
1 0 0 0 1
1 1 0 1 1

Si \(A\) es un conjunto, se define la función característica de \(A\), \(\chi_A\), como el predicado:

\(\chi_A(x)= \begin{cases}
1 & \text{si \(x\in A\)},\\
0& \text{si \(x \notin A\)}
\end{cases}\)

Recíprocamente, si \(P\) es un predicado, podemos definir el conjunto: \(A_P=\{x: P(x)=1\}\), verificándose:

\(A_{\chi_A}=A,\ \ \chi_{A_P}=P\)

Basándose en esta última identificación, de las propiedades vistas sobre conjuntos se tendría:

\(A_{P\wedge Q}=A_P \cap A_Q,\quad A_{P\vee Q}=A_P \cup A_Q,\quad A_{\neg P}=\overline{A_P}\)
\(P \wedge Q \Leftrightarrow \neg(\neg P \vee \neg Q)\)
\(P \vee Q \Leftrightarrow \neg(\neg P \wedge \neg Q)\)

Nota: Las operaciones aquí definidos como \(\neg P,\ P\wedge Q\), y \(P\vee Q\), se pueden expresar desde el punto de vista funcional como composiciones entre funciones adecuadas.

Cuantificadores

Definición: Dado un predicado, \(P\), sobre \({\Bbb N}^{k+1}\), el predicado, \(Q_1\), definido sobre \({\Bbb N}^{k+1}\) como:

\(Q_1(y,x_1,...,x_n)=\begin{cases}
1& \text{ si existe } t\leq y \mbox{ tal que }P(t,x_1,,...,x_n),\\
0& \text{en caso contrario.}
\end{cases}\)

se dice que se obtiene por cuantificación existencial acotada a partir de \(P\), y se denota: \((\exists t)_{\leq y}\ P(t,x_1,...,x_n)\).

Definición: Análogamente, el predicado, \(Q_2\), definido sobre \({\Bbb N}^{k+1}\) como:

\(Q_2(y,x_1,...,x_n)=\begin{cases}
1& \text{ si para todo } t\leq y\mbox{ se tiene que }P(t,x_1,,...,x_n),\\
0& \text{en caso contrario.}
\end{cases}\)

se dice que se obtiene por cuantificación universal acotada a partir de \(P\), y se denota: \((\forall t)_{\leq y}\ P(t,x_1,...,x_n)\).

Definición: Dado un predicado, \(P\), sobre \({\Bbb N}^{k+1}\), el predicado, \(Q_3\), definido sobre \({\Bbb N}^k\) como:

\(Q_3(x_1,...,x_n)=\begin{cases}
1 & \text{ si existe } t\mbox{ tal que }P(t,x_1,,...,x_n),\\
0& \text{en caso contrario.}
\end{cases}\)

se dice que se obtiene por cuantificación existencial a partir de \(P\), y se denota: \((\exists t)\ P(t,x_1,...,x_n)\).

Definición: Análogamente, el predicado, \(Q_4\), definido sobre \({\Bbb N}^k\) como:

\(Q_4(x_1,...,x_n)=\begin{cases}
1& \text{ si para todo } t\mbox{ se tiene que }P(t,x_1,,...,x_n),\\
0& \text{en caso contrario.}
\end{cases}\)

se dice que se obtiene por cuantificación universal a partir de \(P\), y se denota: \((\forall t)\ P(t,x_1,...,x_n)\).

Alfabetos, Cadenas y Lenguajes

Un alfabeto será un conjunto no vacío, \(\Sigma\), cuyos elementos denominaremos símbolos.

Una cadena (o palabra) de \(\Sigma\) será una tupla de elementos de \(\Sigma\), pero en vez de notarla \((a_1,...,a_n)\), escribiremos directamente: \(a_1...a_n\).

Si \(u=a_1...a_n\), diremos que su longitud es \(n\), y se escribirá: \(|u|=n\). Como caso especial, permitimos una palabra de longitud \(0\), llamada palabra vacía, y que se notará por \(\lambda\).

Al conjunto de todas las palabras de \(\Sigma\) se le nota \(\Sigma^*\), obteniéndose que: \(\Sigma^*=\cup_{n\geq 0} \Sigma^n\).

Podemos definir una función de concatenación en \(\Sigma^* \times \Sigma^*\) por:

\(u=a_1...a_n,\ v=b_1...b_k \rightarrow u\cdot v=a_1...a_n b_1...b_k\)

Muchas veces se escribirá \(uv\), por \(u\cdot v\). Y se verifica:

\(\lambda u=u \lambda =u,\ (uv)w=u(vw)\)

\(uv=uw \rightarrow v=w\)

Notaremos: \(u^n=\underbrace{u\cdot ...\cdot u}_{n\ veces}\), \(\quad u^0=\lambda\)

Diremos que \(u\) es subcadena de \(v\) si existen dos palabras \(x,y\) tales que: \(xuy=v\) (pudiendo ser alguna de ellas \(\lambda\)). Si \(v=xy\), diremos que \(x\) es prefijo de \(v\) y que \(y\) es sufijo de \(v\).

Pruebas Matemáticas

Reducción al absurdo

Este método de demostración se basa en suponer que la proposición que queremos probar es falsa, y a continuación, usando su negación como punto de partida, obtener una contradicción. Como consecuencia, la proposición que queríamos probar es cierta.

Ejemplo: \(\sqrt{2}\) es irracional.

Observación previa: Si \(m^2\) es par, entonces \(m\) es par. Para probar esta observación basta notar que los factores primos de \(m^2\) son los mismos que los de \(m\), con exponente doble.

Demostración. Supongamos lo contrario, es decir, supongamos que

\(\exists m\exists n\ ((\sqrt{2} = \frac{m}{n})\)

Podemos suponer que \(\frac{m}{n}\) es irreducible. Así, tenemos \(m^2=2n^2\); por tanto, \(m^2\) es par, luego por la observación anterior, \(m\) es par, esto es, existe \(k\) tal que \(m=2k\), de donde \(m^2=4k^2=2n^2\), y por tanto \(2k^2=n^2\), es decir, \(n^{2}\) es par, luego \(n\) es par!!!. Lo que contradice la irreducibilidad de \(\frac{m}{n}\).

Principio de Inducción Débil

Dado \(P\), predicado sobre los número naturales, si se verifica:

  1. \(P(0)\) (es decir, \(0\) verifica el predicado), y además
  2. Para cada \(n \in {\Bbb N}\), si se tiene \(P(n)\), entonces se tiene \(P(n+1)\).

Entonces, para todo \(n \in {\Bbb N}\) se verifica \(P(n)\).

Ejemplo: \( 1+...+n=\frac{n(n+1)}{2}\)

Demostración: Por inducción débil sobre \(n\):

El caso \(n=0\) es obvio, ya que \(0=\frac{0\cdot(0+1)}{2}\).

Para el caso \(n\rightarrow n+1\) supongamos que \(1+...+n=\frac{n(n+1)}{2}\), entonces: 

$\begin{array}{cc}1+...+n+(n+1)=&(1+...+n)+(n+1)=(\mbox{Hip. inducción})=\\
&\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}\end{array}$

Por lo que el Principio de Inducción nos asegura que la fórmula anterior es válida para todo valor de \(n\in {\Bbb N}\).

Nota: Si en vez de verificarse \(P(0)\), tenemos que se verifica \(P(a)\), para cierto \(a\in {\Bbb N}\), entonces el resultado que se obtiene es: \(\forall n\geq a\ P(n)\).

Principio de Inducción Fuerte

Dado \(P\), predicado sobre los número naturales, si se verifica:

  1. \(P(0)\) (es decir, \(0\) verifica el predicado), y además
  2. Para cada \(n \in {\Bbb N}\): si se verifica \(P(m)\), para todo \(m<n\) entonces se verifica \(P(n)\).

Entonces, para todo \(n \in {\Bbb N}\) se verifica \(P(n)\).

Ejemplo: Todo número natural, \(n\geq 1\), se puede descomponer en producto de primos.

Demostración: Lo haremos por inducción fuerte sobre \(n\):

Si \(n=2\) Es obvio, ya que \(2\) es primo.

Para el caso inductivo, supongamos que para todo \(m<n\), \(m\) se puede descomponer en producto de primos. Puede ocurrir:

  1. Caso 1: \(n\) primo. Por lo que ya sería producto de primos.
  2. Caso 2: \(n\) no primo, por lo que existen \(m_1,m_2\), con \(1<m_1,m_2<n\) tales que \(n=m_1 m_2\). Por hipótesis de inducción aplicada sobre \(m_1\), \(m_2\), se tiene que \(m_1=p_1 \cdots p_k\), \(m_2=q_1 \cdots q_l\), donde los \(p_i,q_j\) son primos, y por tanto \(m=p_1 \cdots p_k q_1 \cdots q_l\) es producto de primos. 

Nota: Si en vez de verificarse \(P(0)\), tenemos que se verifica \(P(a)\), para cierto \(a\in {\Bbb N}\), entonces el resultado que se obtiene es: \(\forall n\geq a\ P(n)\).

Principio del menor elemento

Dado \(A\subseteq {\Bbb N}\), con \(A{\Bbb N}eq \emptyset\), entonces existe \(m=min(A)\); es decir, existe \(m \in A\) tal que \(\forall x \in A (m\leq x)\).

Ejemplo: Todo número natural mayor que \(1\) es primo o tiene un divisor primo.

Demostración: Dado \(n\geq 2\), definimos

\(A_n=\{m\in {\Bbb N}:\ 1<m\leq n \wedge m \mbox{ divide a } n\}\)

Es evidente que \(A_n\neq \emptyset\), ya que \(n\in A_n\). Por tanto, aplicando el Principio del menor elemento, existe \(p=\min (A_n)\). Veamos que \(p\) es primo:

Si \(q\leq p\ (1<q)\) y divide a \(p\), entonces \(q\) divide a \(n\), y por tanto \(q \in A_n\). Pero debido a que \(p=\min (A_n)\), se deduce que \(q=p\). De donde se obtiene que los únicos divisores de \(p\) son \(1\) y \(p\), es decir, que \(p\) es primo.

Si \(A_n=\{n\}\), entonces \(p=n\) y \(n\) es primo. Si no es así, entonces \(n\) tiene un divisor primo.

Nota: Los tres principios anteriores son equivalentes, es decir, a partir de cualquiera de ellos se pueden probar los otros dos.

Cardinalidad

Definición: Dos conjuntos, \(A,B\), diremos que tienen el mismo cardinal, si existe una aplicación biyectiva entre ellos.

Definición: Un conjunto, \(A\), diremos que es finito, si existe \(n\in {\Bbb N}\) de forma que \(A\) y \(\{1,2,...,n\}\) tienen igual cardinal. En este caso se dirá que el cardinal de \(A\) es \(n\).

Definición: Un conjunto se dirá infinito cuando no sea finito.

Definición: Un conjunto, \(A\), se dirá numerable si tiene el mismo cardinal que \({\Bbb N}\) (en particular, dicho conjunto es infinito), es decir, existe \(f:{\Bbb N} \to A\) biyectiva.

Nota:

  • Un conjunto infinito puede tener el mismo cardinal que un subconjunto propio suyo (por ejemplo, \({\Bbb N}\) y el conjunto de los pares). Pero esta posibilidad no se da en los conjuntos finitos.
  • \({\Bbb N}, {\Bbb Z} , {\Bbb N}^2\) y \({\Bbb Q}\) tienen el mismo cardinal, es decir, todos ellos son numerables. Una función biyectiva que numera \({\Bbb N}^2\) es la llamada función \(J\) de Cantor, que tiene la expresión: $$J(x,y)=\frac{(x+y)(x+y+1)}{2}+x$$
  • \({\cal{P} }({\Bbb N})\) no es numerable, en consecuencia, \({ \mathbb{R} }\) no es numerable, es decir, que no existe ninguna biyección entre los números naturales y los números reales.

El concepto intuitivo de algoritmo

Primer intento

Un algoritmo, \(A\), es una sucesión finita de instrucciones \(I_1,...,I_n\), que para cada dato de entrada, \(x\), nos proporciona al cabo de un número finito de pasos un dato de salida, que denominamos resultado de aplicar el algoritmo \(A\) sobre \(x\), y denotamos \(A(x)\)

Nota:

  • Un algoritmo debe proporcionar, a partir de un dato de entrada \(x\), un resultado mediante un procedimiento totalmente mecánico, que pueda ser llevado a cabo por un ordenador.
  • Un algoritmo debe poder representarse a partir de una cadena finita de caracteres en un alfabeto finito.
  • Cada una de las instrucciones de un algoritmo debe especificar de manera precisa una operación efectiva, es decir, que debe poder realizarse en un tiempo finito y con unos recursos finitos (espacio).

Ejemplos:

1. La división euclídea: daremos dos procedimientos, uno que calcule el cociente, \(Q\), y otro para calcular el resto, \(R\):

Q : Entrada : = (m,n) de N^2 (n>0)
Para k=0 hasta m hacer
Si (k+1)n>m entonces devolver k y parar.
Fin Para.
R :Entrada : (m,n) de N^2 (n>0)
Hallar Q(m,n)
q <- Q(m,n)
Devolver m-nq y parar.

2. El siguiente ejemplo usa los algoritmos anteriores para comprobar si un número es primo:

P :Entrada : n de N (n>1)
Para k=2 hasta n-1 hacer
Si R(n,k)=0\entonces devolver NO y parar.
Fin Para
Devolver SI.

3. Como ejemplo de un algoritmo que no trabaja con números damos el siguiente de ordenación alfabética de cadenas. Para ello, suponemos dado un alfabeto finito, \(\Sigma\), en el que los símbolos tienen un orden dado (por ejemplo, piénsese en el alfabeto con la ordenación habitual). Dadas dos palabras \(u,v\) sobre dicho alfabeto, el orden de los símbolos induce un orden sobre las palabras, similar al que se utiliza en los diccionarios. El siguiente algoritmo, dadas \(u,v\) devuelve el valor del predicado \(u<v\):

ALF :Entrada : u=u_1...u_n, v=v_1...v_m
k <- min(n,m)
Para i=1 hasta k hacer
Si u_i<v_i entonces devolver SI y parar.
Si v_i<u_i entonces devolver NO y parar.
Fin Para.
Si n<m entonces devolver SI y parar.
Devolver NO y parar.

4. Una variante para ordenar las palabras es hacer que aparezcan primero las que sean más cortas, para ello:

VAR :Entrada : u=u_1...u_n, v=v_1...v_m
Si n<m entonces devolver SI y parar.
Si m<n entonces devolver NO y parar.
ALF(u,v)

Vamos a restringirnos a algoritmos que trabajen sobre números naturales. Puesto que los algoritmos vienen descritos por una sucesión de caracteres en un alfabeto finito fijo, podemos ordenar las palabras de dicho alfabeto, usando el algoritmo VAR, descrito anteriormente, asignándole a cada algoritmo el número correspondiente a la posición que ocupa. Además, y lo que es de vital importancia, la forma en que somos capaces de asignar a cada algoritmo su número y viceversa (es decir, conocido el número, decodificarlo para obtener el algoritmo correspondiente) es un proceso mecanizable, es decir, que se puede calcular de manera efectiva por medio de un algoritmo.

Supongamos que \(A_0,A_1,...,A_n,...\) es la numeración de los algoritmos codificados. Es decir, \(A_k\) es el algoritmo que ocupa la posición \(k\)-ésima. En este caso, podemos definir el siguiente algoritmo:

D :Entrada : n de N
Hallar A_n
Calcular A_n(n)
Devolver A_n(n)+1 y Parar.

Como \(D\) es un algoritmo que recibe como entrada un número natural, y devuelve un número, debe aparecer en la enumeración de los algoritmos que dimos anteriormente, es decir, existe \(e \in {\Bbb N}\) tal que \(D=A_e\), pero en este caso: \(D(e)=A_e(e)\); y por otra parte, por la definición de \(D\), \(D(e)=A_e(e)+1\).

Esto es: \(A_e(e)+1=A_e(e) \rightarrow 1=0\ !!!\), lo que nos lleva a una contradicción.

Si analizamos todo lo dicho anteriormente, observamos que la contradicción se debe a que la definición intuitiva de algoritmo que hemos dado no es la apropiada, ya que no podemos exigir que un algoritmo pare siempre sobre cualquier dato de entrada y mantener simultáneamente la exigencia de que sea posible describir los algoritmos como cadenas de caracteres de un alfabeto finito fácilmente reconocibles. Esto nos lleva a modificar nuestra definición, permitiendo que incluya la posibilidad de que, en ciertos datos de entrada, el algoritmo no proporcione ningún resultado:

Segundo intento

Un algoritmo, \(A\), es una sucesión finita de instrucciones \(I_1,...,I_n\), que al recibir un dato de entrada, \(x\), especifican:

  1. Qué operación (efectiva) ha de realizarse.
  2. Cuál es la siguiente instrucción que debe llevarse a cabo. Si tal instrucción no existe, decimos que el algoritmo para y debe, entonces, proporcionar un dato de salida, o resultado, que notaremos por \(A(x)\).

Nota: Dado \(x\), escribiremos \(A(x)\downarrow\) para indicar que el algoritmo \(A\) para sobre el dato de entrada \(x\), y \(A(x)\uparrow\) para indicar que no para.

« Cuadernos del CIS: Si… « || Inicio || » TC: Programas y Funci… »