Maquina Turing
Tese de Church-Turing
Variantes e extens˜ oes M´ aquina de Turing Universal
Programa¸c˜
ao com M´ aquinas de Turing
Teoria da Computa¸c˜ao
M´aquinas de Turing
Sim˜
ao Melo de Sousa
Computer Science Department
University of Beira Interior, Portugal
S. Melo de Sousa
Teoria da Computa¸c˜ ao Introdu¸c˜ ao Defini¸c˜ ao Linguagens e M´ aquinas de Turing
Tese de Church-Turing
Variantes e extens˜ oes M´ aquina de Turing Universal
Programa¸c˜
ao com M´ aquinas de Turing
Plano
1
Introdu¸c˜ ao 2
Defini¸c˜ ao O que ´e uma m´ aquina de Turing?
O Processo de Execu¸c˜ ao 3
Linguagens e M´ aquinas de Turing
Linguagem Aceite e Linguagem Decidida
Linguagem Decidida e Aut´ omatos Linguagens Recursivas e Linguagens Recursivamente Numer´ aveis 4
Tese de Church-Turing
Fun¸co
˜es Comput´ aveis 5
Variantes e extens˜ oes 6
M´ aquina de Turing Universal
7
Programa¸c˜ ao com M´ aquinas de Turing
S. Melo de Sousa
Teoria da Computa¸c˜ ao Introdu¸c˜ ao Defini¸c˜ ao Linguagens e M´ aquinas de Turing
Tese de Church-Turing
Variantes e extens˜ oes M´ aquina de Turing Universal
Programa¸c˜
ao com M´ aquinas de Turing
Aviso Pr´evio
A redac¸c˜ ao dos apontamentos da disciplina documento baseou-se fortemente na bibliografia indicada. Parece-nos ent˜ ao ´ obvio que a leitura e a aprendizagem directa pelas obras originais ´ e recomendada, e mesmo essencial ` a compreens˜ ao profunda das no¸c˜ oes aqui apresentadas; O portuguˆ es n˜ ao ´ e a l´ıngua materna do autor e o presente documento encontra-se em fase (constante) de elabora¸c˜ ao/melhoramento pelo que se agradece e at´ e se incentiva qualquer sugest˜ ao ou correc¸c˜ ao; S. Melo de Sousa
Teoria da Computa¸c˜ ao Introdu¸c˜ ao Defini¸c˜ ao Linguagens e M´ aquinas de Turing
Tese de Church-Turing
Variantes e extens˜
oes