Personalização de programas no simulador da Máquina de Turing

Paula Gouveia / IEEE-IST Student Branch / maio 2012

Máquina de Turing é um tuplo\[M=(Q,\Sigma,\Gamma,\delta, q_0,q_a,q_r)\]onde

  • \(Q\) é um conjunto finito (o conjunto dos estados);
  • \(\Sigma\) é um conjunto finito (alfabeto de entrada);
  • \(\Gamma\) é um conjunto finito (alfabeto da fita) tal que \(\Sigma\cup\{\_\}\subseteq \Gamma\) em que \(\_\notin \Sigma\) é o simbolo de registo vazio;
  • \(\delta:Q\times\Gamma \rightarrow Q\times\Gamma\times \{L,R\}\) é uma função total (função de transição);
  • \(q_0\in Q\) é o estado inicial;
  • \(q_a\in Q\) é o estado de aceitação;
  • \(q_r\in Q\) é o estado de rejeição e \(q_r\not = q_a\).

Uma Máquina de Turing pode ser vista como um modelo abstracto de um computador digital, mas foi proposta muito antes da existência dos computadores pelo matemático inglês Alan Turing nos anos 30 do século XX, no âmbito dos seus trabalhos sobre Computabilidade. Os resultados por ele estabelecidos permitem-nos tirar conclusões sobre os limites da capacidade computacional dos computadores digitais. Apesar de simples, as máquinas de Turing podem simular qualquer cálculo efectuado por um computador digital.

A noção de Máquina de Turing é também central no estudo da Complexidade Computacional.