===== MÁQUINA DE TURING =====
A [[lexico:n:nocao|noção]] de "[[lexico:m:maquina-de-turing|máquina de Turing]]", enquanto "[[lexico:m:maquina|máquina]] [[lexico:m:matematica|matemática]], surgiu como uma tentativa de fornecer um equivalente [[lexico:f:formal|formal]] [[lexico:a:adequado|adequado]] para o [[lexico:p:processo|processo]] [[lexico:h:humano|humano]] de computação "[[lexico:m:mecanica|mecânica]]". A máquina matemática deveria funcionar como um débil mental a [[lexico:q:quem|quem]] houvessem sido dadas instruções para a execução de uma certa [[lexico:t:tarefa|tarefa]], e que nesta execução cumprisse mecânica e rigorosamente as instruções dadas. Baseado nesta [[lexico:i:ideia|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|cálculo]] de uma [[lexico:f:funcao|função]] (por [[lexico:e:exemplo|exemplo]], o [[lexico:v:valor|valor]] de A dividido por B) deve poder [[lexico:s:ser|ser]] analisado numa [[lexico:s:sucessao|sucessão]] finita de etapas elementares ("separe tantas casas decimais do dividendo quantas houverem no divisor"; "veja qual o maior [[lexico:m:multiplo|múltiplo]] do divisor nestas casas", e assim por diante). Uma etapa consiste no exame de um certo [[lexico:e:estado|Estado]] dos cálculos — um exame do [[lexico:s:simbolo|símbolo]] [[lexico:e:escrito|escrito]] na fita —; uma [[lexico:d:decisao|decisão]] a [[lexico:r:respeito|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|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|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|memória]] (potencialmente) infinita, e tendo à sua [[lexico:d:disposicao|disposição]] um [[lexico:t:tempo|tempo]] (potencialmente) [[lexico:i:infinito|infinito]] para efetuar os cálculos. Estes cálculos, no entanto, devem ser efetivados num [[lexico:n:numero|número]] [[lexico:f:finito|finito]] de etapas. O programa de um [[lexico:c:computador|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|representação]] de um processo [[lexico:m:mecanico|mecânico]] de computação, até hoje, são equivalentes ao [[lexico:m:modelo|modelo]] da máquina Turing. (Francisco Doria - [[lexico:d:dcc|DCC]]).