Lenguas Y Autonomas

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing.
Esconveniente suponer que un sistema computacional es fijo (abstracto), con la finalidad de eliminar las variaciones de un sistema a otro. Brookshear elimina estas variaciones de análisis en sistemas diferentesy evalúa la complejidad de cálculo suponiendo un sistema fijo basado en una máquina de Turing, ya que supone que a partir de ella puede trasladar sus resultados a otros sistemas y mantener lacomplejidad.
Un lenguaje de programación (el preferido por usted) tiene un poder expresivo ya que permite escribir cualquier algoritmo (una idea) en ese lenguaje. Sin embargo, suponemos que existen algunosalgoritmos que no pueden representarse haciendo uso de ese lenguaje. Surge la interrogante de si esto se debe a una limitación del lenguaje o es una limitación de los procesos algorítmicos en general(no existe algoritmo). Nos preguntamos, si el lenguaje no permite escribir un algoritmo o es que no existe un algoritmo que pudiera calcular dicha función. Consideremos una clase que contiene todaslas funciones computables. Una función es computable si existe un algoritmo para ella, sin importar como pueda implantarse o expresarse ese algoritmo. Puede construirse un conjunto que contenga todaslas funciones computables, para ello se utiliza un método muy usado por los matemáticos, el método recursivo generacional. Este método permite que a partir de un conjunto básico de funcionescomputables, consideradas como funciones iniciales, puedan construirse las demás combinándolas en forma recursiva y así obtener el conjunto mayor de todas las funciones computables. Puede demostrarse, aunque noes el objetivo de este artículo, que una función de esta clase puede calcularse por medio de una máquina de Turing. La Teoría de la Complejidad Computacional se basa en un enfoque no funcional, en...