#6 Teorema de la computación
Teoremas sobre las máquinas de Turing
Lenguaje Recursivamente Enumerable
Recordemos que llamamos
lenguaje Recursivamente Enumerable (RE) a los
lenguajes que pueden ser aceptados por una Máquina de Turing.
Teorema
1
Todo lenguaje aceptado por una
Máquina de Turing de varias cintas es Recursivamente Enumerable.
Teorema
2
Sea L = L(M) el
lenguaje que acepta una máquina de Turing no determinista M,
entonces existe una máquina de Turing deterministaN que acepta
dicho lenguaje, es decir, L(M) =L (N).
Lenguajes de máquinas de Turing y de Autómatas
Teorema
3
Sea L el
lenguaje aceptado por una máquina de Turing, entonces existe algún Autómata de
dos pilas que acepta L.
Teorema
4
Todo lenguaje Recursivamente
Enumerable es aceptado por alguna máquina de tres contadores.
Teorema
5
Todo lenguaje Recursivamente
Enumerable es aceptado por alguna máquina de dos contadores.
No hay comentarios:
Publicar un comentario