===== MÁQUINA DE TURING =====
A [[lexico:n:nocao:start|noção]] de "[[lexico:m:maquina-de-turing:start|máquina de Turing]]", enquanto "[[lexico:m:maquina:start|máquina]] [[lexico:m:matematica:start|matemática]], surgiu como uma tentativa de fornecer um equivalente [[lexico:f:formal:start|formal]] [[lexico:a:adequado:start|adequado]] para o [[lexico:p:processo:start|processo]] [[lexico:h:humano:start|humano]] de computação "[[lexico:m:mecanica:start|mecânica]]". A máquina matemática deveria funcionar como um débil mental a [[lexico:q:quem:start|quem]] houvessem sido dadas instruções para a execução de uma certa [[lexico:t:tarefa:start|tarefa]], e que nesta execução cumprisse mecânica e rigorosamente as instruções dadas. Baseado nesta [[lexico:i:ideia:start|ideia]], o matemático inglês Alan Turing propôs em 1936 a seguinte formulação como sendo um substitutivo formal adequado para a noção de "computabilidade". Seja uma máquina. Esta máquina vai realizar os seus cálculos numa fita (potencialmente) infinita, e dividida transversalmente em quadrados sucessivos. Como serão feitos os cálculos? O [[lexico:c:calculo:start|cálculo]] de uma [[lexico:f:funcao:start|função]] (por [[lexico:e:exemplo:start|exemplo]], o [[lexico:v:valor:start|valor]] de A dividido por B) deve poder [[lexico:s:ser:start|ser]] analisado numa [[lexico:s:sucessao:start|sucessão]] finita de etapas elementares ("separe tantas casas decimais do dividendo quantas houverem no divisor"; "veja qual o maior [[lexico:m:multiplo:start|múltiplo]] do divisor nestas casas", e assim por diante). Uma etapa consiste no exame de um certo [[lexico:e:estado:start|Estado]] dos cálculos — um exame do [[lexico:s:simbolo:start|símbolo]] [[lexico:e:escrito:start|escrito]] na fita —; uma [[lexico:d:decisao:start|decisão]] a [[lexico:r:respeito:start|respeito]] do que deve ser feito em seguida; e a execução do que foi decidido. Uma máquina de Turing poderá ser representada por um conjunto de instruções da seguinte [[lexico:f:forma:start|forma]]: ci aj bk cl

Suponhamos que a máquina esteja no estado ci. Ela "observa", na fita, o símbolo aj escrito. Sua tabela de instruções diz, no caso, que ela deve "tomar a [[lexico:a:atitude:start|atitude]]" bk (esta atitude pode ser: caminhar para a direita, caminhar para a esquerda, parar, apagar aj e escrever uma letra an). Ela toma essa atitude e passa para o estado cl. Em sua tabela de instruções haverá uma linha começando por cl, e a máquina começa outra etapa de sua computação.

Máquinas de Turing podem ser vistas como computadores eletrônicos possuindo uma [[lexico:m:memoria:start|memória]] (potencialmente) infinita, e tendo à sua [[lexico:d:disposicao:start|disposição]] um [[lexico:t:tempo:start|tempo]] (potencialmente) [[lexico:i:infinito:start|infinito]] para efetuar os cálculos. Estes cálculos, no entanto, devem ser efetivados num [[lexico:n:numero:start|número]] [[lexico:f:finito:start|finito]] de etapas. O programa de um [[lexico:c:computador:start|computador]] é equivalente à "tabela de instruções" da máquina de Turing.

Pode-se mostrar como todos os sistemas e modelos propostos para a [[lexico:r:representacao:start|representação]] de um processo [[lexico:m:mecanico:start|mecânico]] de computação, até hoje, são equivalentes ao [[lexico:m:modelo:start|modelo]] da máquina Turing. (Francisco Doria - [[lexico:d:dcc:start|DCC]]).

{{indexmenu>.#1|skipns=/^playground|^wiki/ nsonly}}