Page 34 - 06 Turing

zado como tesis de Church-Turing. En un lenguaje actual, su tesis
establece que la clase de problemas que puede resolver una má-
quina de Turing universal, y por tanto un ordenador, son los que
su solución pueda ser expresada por medio de un algoritmo. No
obstante, hay que tener en cuenta que en aquella época el vocablo
algoritmo no se utilizaba aún, y para referirse a este concepto
lo hacían con la expresión «método efectivo de computación».
Podemos definir un algoritmo como el cortjunto de pasos o reglas
que conducen al resultado o solución de un problema. Por consi-
guiente, para un ordenador un algoritmo es sinónimo de solución.
Todo algoritmo debe cumplir ciertas propiedades:

- En primer lugar, el número de pasos que conducen a la
solución ha de ser finito, es decir, el protocolo que se re-
corre hasta la solución debe concluir siempre, por largo
que sea.

- En segundo lugar, los pasos o reglas deben estar bien de-
finidos, sin ambigüedades. Para ilustrar esta idea, consi-
dérese, por ejemplo, un sencillo experimento escolar
consistente en «medir el número re»: primero, rodearemos
una lata cualquiera con una cinta de papel, cortando el
material sobrante de la cinta; segundo, retiramos la cinta
de papel y medimos con una regla su longitud; tercero, si-
tuamos la lata entre dos libros, midiendo la distancia entre
los bordes de los libros en contacto con la lata para obte-
ner su diámetro, y cuarto, calculamos el cociente entre la
longitud y el diámetro, el valor obtenido es el valor de re.

- En tercer lugar, aunque este es un requisito opcional, lo
ideal será que un algoritmo pueda resolver no un pro-
blema concreto, sino problemas de una misma clase, por
ejemplo, ordenar palabras alfabéticamente.

- Y en cuarto lugar, también requisito opcional, que el ca-
mino hasta la solución conste del menor número posible
de pasos.

34 WUÉ ES UN ORDENADOR?