Fundamentos de algoritmos

Fundamentos de algoritmos.
5.1 La compatibilidad y concepto de algoritmo: Máquina de Turing. Computabilidad consiste en encontrar la representación adecuada para la descripción de un problema o fenómeno, y para esta representación es necesario: un conjunto de símbolos ya sean números letras, entre otros, encontrar la combinación adecuada de los símbolos, es decir, formular un código, crear unaforma para demostrar que eso es cierto y que otras personas puedan reproducirlo y llegar a las mismas conclusiones.
Para poder representar el problema o fenómeno el computador seguirá el procedimiento para resolverlo basado en un algoritmo en cual lo guiara para poder resolverlo de la manera más rápida y efectiva; entiéndase por algoritmo la receta o secuencia de pasos que se deben de seguir parapoder solucionar el problema esto implica que los pasos o reglas sean bien definidas, estén ordenadas y sean finitas esto para no generar dudas a quien deba de realizar dicha actividad. Todos los usuarios sabemos que las computadoras pueden realizar determinados procesos que nos facilitan muchas tareas por ejemplo, por medio de algoritmos controlar el tráfico aéreo, controlar los ingresos en unaempresa o hasta cosas insignificantes como preparar alguna comida.
Todas las funciones construidas por recursividad primitiva o minimalización a partir de funciones calculables resultan ser calculables como consecuencia de los trabajos de Church y Turing. Pero además, otras funciones más complejamente definidas también son computables, siendo el resultado más significativo en relación con estacuestión el dado por el siguiente teorema:
Primer teorema de Recursión: Todo operador entre funciones calculables que sea recursivo (esto es que se defina la imagen de f mediante una función calculable en términos de una parte finita de f), tiene una función parcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es unaextensión de esa función. A menudo se utiliza la técnica de reducir un problema a otro para comprobar si tiene o no solución efectiva. La estrategia en el caso de la respuesta negativa es la siguiente, si se reduce de forma efectiva un problema sin solución efectiva a otro problema (mediante una función calculable), entonces este nuevo problema tampoco tendrá solución efectiva. La razón es muy simple, situviese solución efectiva, componiendo el algoritmo solución con el algoritmo de transformación obtendríamos una solución para el problema efectivamente irresoluble. En sentido inverso, si se reduce un problema a otro para el que se conoce una solución efectiva, entonces componiendo se obtiene una solución para el primer problema. Esta técnica es muy útil y se utiliza a menudo. Por otro lado, estamisma técnica es muy empleada en el campo de la complejidad algorítmica. Para asegurarse de que un problema está en una clase de complejidad, basta reducir el problema a otro de dicha clase sin más que asegurarse que la reducción se realiza en la correspondiente clase de complejidad.
Es un conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. Método y notaciónen las distintas fórmulas del cálculo. El algoritmo constituye un método para resolver un problema mediante una secuencia de pasos a seguir. Dicha secuencia puede ser expresada en forma de diagrama de flujo con el fin de seguirlo de una forma más sencilla.
Es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina deTuring puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico. La máquina de Turing consistía en una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con...