Monografías Plus      Agregar a favoritos      Ayuda      Português      Ingles     

Máquinas de Turing

Enviado por Pablo Turmero



Partes: 1, 2, 3

Monografias.com
Algoritmos: Orígenes de la palabra Al-Khwarizmi, astrónomo y matemático persa, escribió en 825 un tratado en árabe sobre el Cálculo con Cifras Indúes, que se tradujo al latín en el siglo XII como Algoritmos con números indios. La raíz es la misma que la de la palabra Álgebra.
Monografias.com
Algoritmos: Definición y tipos Conjunto de instrucciones (en un lenguaje entendido por “la computadora”, una máquina o persona) que especifica las operaciones para procesar una información de entrada arbitraria, y producir una información de salida deseada. Información: Datos (números, cadenas de caracteres) Tipos de algoritmos: Procedimientos para realizar tareas, recetas de cálculo, …
Monografias.com
Diversidad de tipos de datos Los tipos de datos que se utilizan en los distintos mecanismos computacionales son equivalentes: cadenas de caracteres, números en diferentes representaciones, ... (excepción: el Lambda-Cálculo) La equivalencia anterior no es válida si nos interesa la eficiencia algorítmica. Otros tipos de datos no se pueden (o no se saben) tratar computacionalmente: estado instantáneo de un ser vivo, …
Monografias.com
Tipos de datos Los programas son datos y definen funciones Normalmente usaremos cadenas de caracteres A menudo nos restringiremos a cálculos sobre cadenas que son programas Así pues, a menudo los datos serán programas y definirán funciones P(P1, …, Pn): aplicación de la función de P
Monografias.com
Algoritmos: Orígenes del concepto Algoritmos concretos: se conocen desde antes de nuestra era Método de Euclides para calcular el máximo común divisor de dos números Método de Eratóstenes para obtener la lista de los números primos El concepto de algoritmo data del primer tercio del siglo XX.
Monografias.com
Mecanismos computacionales Lenguajes de programación Máquinas de Turing (Turing) y variantes Gramáticas (Chomsky) Funciones recursivas (Gödel, Herbrandt) Lambda-cálculo (Church) Sistemas canónicos de reescritura (Post) Computación cuántica, …
Monografias.com
Mecanismos computacionales, II Algunos de los mecanismos anteriores (lenguajes de programación, máquinas de Turing indeterministas, funciones recursivas, lambda cálculo) se utilizan para definir funciones. Otros (máquinas de Turing indeterministas, gramáticas, reglas de reescritura) se utilizan para reconocer la pertenencia a conjuntos de datos (normalmente cadenas de caracteres).
Monografias.com
Mecanismos computacionales: Funciones Casi todos los mecanismos anteriores permiten definir funciones. Pueden ser funciones sobre cadenas de caracteres, sobre números o sobre funciones A veces al calcular el valor de la imagen de un dato (cadena, número o función) mediante una función no se obtiene ningún valor porque el cálculo nunca termina Las funciones definidas a partir de mecanismos computacionales son funciones parciales sobre un dominio universal (?*, ?, ?)
Monografias.com
Mecanismos computacionales: Funciones, II Distintos programas pueden definir la misma función. Por ejemplo, hay infinitos programas que nunca paran, y todos ellos definen la función de dominio vacío. No todas las funciones en el sentido matemático se pueden definir a partir de un mecanismo computacional. Lo veremos más adelante.
Monografias.com
Mecanismos computacionales: Funciones, III Ejemplo: Dada una máquina de Turing M con alfabeto ?, definimos la función an, si M para sobre w f(w) = ? en caso contrario donde n es el número de pasos que da la máquina antes de pararse a partir de w. A priori no está claro cómo definir f mediante un mecanismo computacional.
Monografias.com
Mecanismos computacionales: Funciones, IV El ejemplo anterior tiene trampa: todo depende de cuál sea la máquina M. Por ejemplo, si M calcula a|w| directamen-te, f se calcula mediante la misma M. Si M se mete siempre en un bucle infinito, f se puede calcular mediante la máquina que borra el contenido de la cinta. Hay alguna máquina M para la que f no se puede calcular mediante otra máquina?
Monografias.com
Mecanismos computacionales: Funciones, V Otro ejemplo: Hasta 1995 no se sabía cómo calcular la función f(n), que calcula el “primer” valor no trivial de x, y y z tal que xn+yn=zn a menos que no exista, en cuyo caso le hace corresponder x(n)=0, y(n)=0, z(n)=0. Tras la demostración del teorema de Fermat por Wiles, se sabe que f(2)=(3,4,5) y f(n)=(0,0,0) si n?2.
Monografias.com
Mecanismos computacionales: Funciones, VI Un mecanismo computacional es más potente que otro cuando permite calcular más funciones. Teorema: Las máquinas de Turing, los lenguajes de programación, las funciones recursivas y el cálculo lambda tienen la misma potencia computacional.
Monografias.com
Tesis de Church No hay ningún mecanismo computacional más potente que los anteriores. No es una afirmación demostrable, pues no hay una definición rigurosa y absoluta de mecanismo computacional.
Monografias.com
Lenguajes de programación Qué os puedo decir que no sepáis ya? Pueden entrar en bucles interminables. Es imprevisible cuándo lo hacen. Incluso es imposible distinguir cuándo están dentro de un bucle interminable y cuándo están ejecutando un algoritmo complejo. En teoría permiten definir todas las funciones calculables (o recursivas).
Monografias.com
Lenguajes de programación, II Lenguajes minimales: Variables Tipos de datos básicos (números, cadenas) Operaciones y condiciones básicas (incremento, anteposición, igualdad, …) Instrucciones (asignación, condicional) Etiquetas y redireccionamiento. Posibilidad adicional: Definición de funciones y recursividad.
Partes: 1, 2, 3

Página siguiente 

Comentarios


Trabajos relacionados

Ver mas trabajos de Programacion

 
 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda