lectura_inicial_tc

Vista previa del material en texto

Sesión 1: Marco histórico e importancia de la Teoría
 
 
¿Existe una Teoría en la Computación? 
 
¿Alguna vez se ha preguntado 
"computables"?, es decir, ¿si todo
resueltos con un computador? Se
depende de la complejidad del 
existen problemas fáciles de formula
un computador nunca podrá enco
todas estas dudas se habían come
de construirse el primer computador
 
Cuando se habla de "computable
referencia? ¿Al hecho de reso
computador?, si es así, ¿Cómo lo re
un algoritmo! No obstante la definición de algoritmo, como un
discutible. Podemos considerar un algoritmo como un conjunto 
para, en un número determinado de pasos, llevar a cabo una ta
un algoritmo podría ser llevado a cabo por cualquier persona ut
un lápiz y un papel. El computador también ejecuta acciones
cambian el estado de las variables que representan, o mode
resolver. Todas estas acciones, en una secuencia establecid
obtener información de las entidades y por ende resolver el prob
 
Antes de comenzar a construir el primer computador electrón
ejecutar algoritmos con él, en el año 1936, Alan Turing, m
máquina denominada Máquina de Turing, [1] con el único ob
para poder estudiar la posibilidad de calcular funciones. Graci
pueden analizar los procesos de cálculo en función de la dificul
de esto, conocer las limitaciones de los procesos (problemas 
complejidad (problemas intratables). 
Asignatura: Teoría de la computación 
Unidad 1: Introducción y preliminares 
Tema 1: Marco histórico e importancia 
de la Teoría de la Computación 
 de la Computación 
si todos los problemas son 
s los problemas pueden ser 
guramente piensa que esto 
problema, pero, ¿sabe que 
r para los cuales sencillamente 
ntrar la solución? ¿Sabía que 
nzado a resolver incluso antes 
 electrónico? 
", ¿a qué se está haciendo 
lver un problema con un 
suelve? La respuesta es: ¡con 
 procedimiento específico, es 
finito de instrucciones definidas 
rea determinada. En principio, 
ilizando para ello, por ejemplo, 
 a través de instrucciones que 
lan entidades del problema a 
a, que permite transformar u 
lema. 
ico (1937 a 1942), para poder 
atemático inglés, define una 
jetivo de usarla como modelo 
as a esta estructura teórica, se 
tad de computación, y a partir 
indecidibles), y sus grados de 
Profesora: Hilda Y. Contreras Z.
Asignatura: Teoría de la Computación
Turing quiso hacer esto motivado por el Teorema de la Incompletitud de Gödel [2], pues en 
1931, el mundo de los matemáticos y lógicos se vio revolucionado por sus investigaciones 
sobre las proposiciones formalmente indecidibles de los principios matemáticos y sistemas 
afines, demostrando la incompletitud y la indecibilidad de la aritmética, y además, 
cuestionando pretensiones de formalización de otras áreas del conocimiento como la 
inteligencia artificial. 
 
Turing pudo entonces demostrar que existían funciones que no son posibles calcular en su 
máquina, y luego, con Alonzo Church, planteó, por medio de un axioma, que su poder de 
cálculo es equivalente al del procesamiento del pensamiento humano y, posteriormente, al 
del computador físico (tesis de Church-Turing) [3]. 
 
A partir de este importante modelo, la Máquina de Turing, se generan posteriores 
investigaciones que van descubriendo la jerarquía de los problemas, su complejidad, y los 
modelos asociados a cada tipo de ellos. Esto ha puesto en evidencia que la computación en 
general no es tan pragmática como puede parecer, sino que tiene bases y principios lógicos y 
matemáticos que han permitido deducir, demostrar y comprobar, sus propiedades y 
comportamiento. 
 
Además de este formalismo, Turing, luego de su maravilloso descubrimiento, participa en la 
construcción del primer computador. 
 
Con la Máquina de Turing, nace entonces la Teoría Matemática de la Computación y con ella 
la posibilidad de entender a la Computación como una Ciencia. El término de "teoría", 
altamente polisémico en el uso coloquial (como suposición, falta de concreción, oposición de 
la práctica, como norma, creencia colectiva, opinión o postura frente a un problema, como 
especulación), [4]) comprendida por su carácter científico, establece un conjunto de medios 
de representación conceptual, general y simbólica de un hecho. Además otorga las reglas de 
inferencia que permiten la previsión de los datos del hecho. 
 
Con los conocimientos aportados por Turing, y los que se derivaron luego, se obtuvo como 
resultado un conocimiento descriptivo y explicativo, la Teoría de la Computación, de todo lo 
que puede calcularse en cualquier máquina. Y es a partir de aquí que se puede dar 
respuestas a las preguntas iniciales de este texto. 
 
Referencias: 
Profesora: Hilda Y. Contreras Z.
Asignatura: Teoría de la Computación
 
- A.M. Turing. "On computable numbers with an application to the Entscheidungsproblem". 
Proc. London Mth. Society 2:42 (1936), pp. 230-265. 
 
- K. Gödel, "Uber formal unentscheidbare satze der Principia Mathematica und verwander 
systeme", Monostschefte fur Mathematik und Physik 28 (1931), pp. 173-198. y Nagel Ernest; 
Newman, James R. (1994) El teorema de Gödel. Editorial Tecnos. Madrid. 
 
- Kleene, S.C. (967). Mathematical Logic. New York: Wiley. 
 
- Chacín, M. y Padrón, J. (1994): Investigación y Docencia. Caracas: Publicaciones del 
Decanato de Postgrado, USR http://padron.entretemas.com/ques_teoria.htm 
 
 
Profesora: Hilda Y. Contreras Z.
Asignatura: Teoría de la Computación