Maquina Turing

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

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