juaninf - notas de psudoprogramador

Friday, December 06, 2013

El Faq de las Máquinas de Turing

Este post es sólo un oráculo de algunas preguntas frecuentes para quién ya estudió teoria de la computación y con el tiempo ha ido olvidando algunos conceptos.

Que es una máquina de Turing?
Un Dispositivo
Que es un problema?
Un conjunto de frases de longitud finita que esta asociada a un conjuto de frases también de longitud finita.
Que es un problema decidible?
Un problema que su conjunto asociado solo tiene las frases si y no, es decir existe un método que ya consigue definir esos: si y no. Los problemas decidibles tienen un método definido que consigue decir si el problema(la sentencia) es cierto o falso.
Que es un algoritmo?
No existe un consenso, pero se puede decir que es una máquina de Turing.
Todo método que resuelve un problema decidible puede ser implementado en una máquina de Turing?
no sé. Creo que si.
Que es un problema indecidible?
Un problema para el cual no existe un método tal que sea capaz de resolverlo con una respuesta si o no.
Cuantas programas puedo escribir en una máquina de Turing?
Si es universal muchos, recuerde que una máquina de Turing Universal permite simular cualquier máquina de Turing para cualquier entrada.
Que es PP?
Es la clase de problemas de decisión para los cuáles existe un algoritmo de Montecarlo bilateral que responde si cuando la respuesta correcta es si con probabilidad > 1/2 (idem para no) y el tiempo de ese algoritmo es es un polinómio en el tamaño de la entrada. Otra definición equivalente, es la clase de problemas resolubles por una MT probabilística en tiempo polinomial con probabilidad > 1/2 para todas sus instancias.
NP \in PP?
Si. El problema de la factoración esta en NP, por tanto en PP, entonces existe un algoritmo de montecarlo que consigue factorar como descrito en la pregunta anterior, sólo que máquinas de Turing probabilisticas no existen (en general las no deterministas no existen) y las que se simulan estas no son eficientes, es decir no consiguen factorar en tiempo polinomico.

Post a Comment
Related Posts Plugin for WordPress, Blogger...