Meus autores favoritos (David Deutsch, inglês Roger Penrose, e Douglas Hofstadter) todos aprofundar a Igreja-Turing Tese da Teoria Computacional e, mais importante ainda, as suas mais fortes interpretação: A de Turing Princípio. Neste post, vou primeiro explicar a tese de Church-Turing em termos leigos.
Quando eu estava trabalhando em meu grau de ciência da computação, eu estudei máquinas de Turing e a tese de Church-Turing em minha aula de Introdução à teoria computacional. Naquela altura, pensava que era uma grande perda de tempo. Eu só queria programar computadores e não podia me importar menos com esse Turing morto há muito tempo (nem esse cara da Igreja) nem suas estúpidas máquinas teóricas.Agora que entendo as ramificações filosóficas da tese de Church-Turing, gostaria de ter prestado atenção nas aulas! Porque a tese de Church-Turing, se for verdade, tem algumas profundas ramificações filosóficas e também pode nos dizer algo sobre a natureza profunda e especial da realidade.
autômatos finitos
todos os textos e classes sobre a teoria da Computação começam com algo chamado “autômatos finitos.”A ideia básica por trás deles é muito fácil. Você apenas imagina uma simples ‘máquina’ que é capaz de fazer escolhas e mover-se entre Estados. Aqui está um exemplo de um muito simples que representa a “lógica” de um torniquete operado por moedas.
Na planície inglês, este diz que, se você tentar empurrar através de uma catraca que está bloqueado, você não pode se você ainda não o primeiro coloque em uma moeda. Se você colocou uma moeda, mas ainda não empurrou através, moedas adicionais apenas deixá-lo em um estado desbloqueado. Se você colocou uma moeda, então você pode avançar. Depois tranca novamente para a próxima pessoa.
foi provavelmente mais fácil de entender a partir do diagrama do que a partir da descrição.
autômatos finitos são capazes de executar uma lógica muito mais complicada do que esta. Mas isso deve lhe dar uma sensação básica de como os autômatos finitos funcionam.
Uma coisa a notar é que um autômato finito, como o descrito acima, é puramente teórico, porque ele só existe como um monte de bolhas e linhas em um pedaço de papel. Não é como se houvesse uma pequena “máquina de autômatos finitos” dentro do torniquete que toma essas decisões. Ou talvez deva dizer que o próprio turnstile é a máquina autômato finita.Se realmente quiséssemos, poderíamos provavelmente construir uma máquina na vida real que seria um autômato finito.Não há nada que impeça alguém de a construir como uma máquina real na vida real e depois instalá-la no torniquete. Não é a maneira mais barata de o fazer.
assim qualquer ‘programa’ que você faça como um desenho de um autômato finito pode ser transformado em uma “computação” da vida real que realmente funciona. A importância da diferença entre uma máquina computacional que pode realmente existir (como um Autômato Finito) e outra que é apenas hipotética e viola as leis da física torna-se importante em um momento.
Máquinas Mais Potentes
Como uma classe computacional teoria progride, os alunos são introduzidos cada vez mais complexo “máquinas” que são mais poderosos do que Autómatos Finitos. Como mostra a figura à direita, o próximo mais poderoso é o autômato Pushdown (PDA). Um PDA é realmente apenas um AFD com a adição de uma espécie de “memória”. Esta memória permite que um PDA para criar e executar cálculos (ou programas) que um DFA não pode.
O ponto-chave é apenas que há certos tipos de programas que pode ser escrito para um PDA que não pode ser escrito em um Determinista Autômato Finito (DFA). Em outras palavras PDAs são ‘mais poderosos’ do que DFAs porque eles podem expressar classes de “programas” que DFAs não podem.
então há uma relação entre DFAs e PDAs em termos de “poder computacional”.”Ou seja, é possível provar que qualquer programa escrito em um AFD também pode ser escrito em um PDA, mas que o contrário não é verdade.
A Prova é a Prova
A prova de que um PDA pode executar qualquer coisa que um DFA pode é feito através de um esquema pelo qual a lógica de uma DFA pode ser mapeado para um PDA. Uma vez que um PDA é apenas um AFD com memória, isso não é difícil de fazer — apenas não use o “recurso de memória”.Mas e o contrário? Podemos provar que é impossível pegar certos tipos de “programas” escritos para um PDA e traduzi-los para um AFD? Ou seja, existe uma prova de que autômatos com pilha não podem ser mapeados para um autômato finito? Ou estamos apenas assumindo que um autômato finito é menos poderoso do que um autômato Pushdown porque não sabemos de uma maneira de mapear um PDA de volta para uma FDA? Talvez haja uma maneira de mapear PDAs para FDAs e talvez ninguém tenha descoberto como fazer isso ainda? Não é, pelo menos, uma possibilidade?
ao que parece, é possível provar que um PDA pode executar certos tipos de programas que um AFD não pode. A forma como você faria isso é que você iria encontrar uma computação (i.e. um programa) que você pode provar que um AFD não pode computar e, em seguida, demonstrar que um PDA pode computá-lo.
poder computacional de uma máquina
este facto-que existem máquinas lógicas mais poderosas (PDA) e menos poderosas (DFA) — é interessante por si só.Mas isso leva a uma questão filosófica: existe tal coisa como uma “máquina computacional mais poderosa?”
se houvesse tal “máquina mais poderosa”, como nós saberíamos qualquer máquina proposta específica acontece ser “a mais poderosa?”Ou existem apenas diferentes tipos de máquinas de computação disponíveis e você tem que escolher o certo para o trabalho?
máquinas de Turing
então que máquina é mais poderosa que um PDA?
como a história o teria, ao mesmo tempo, dois tipos muito diferentes de “máquinas” foram propostos que eram ambos provavelmente mais poderosos do que PDAs.
One was Alan Turing’s Turing Machine. O outro não era tanto uma máquina como um conjunto inteligente de anotações desenvolvidas pela Igreja de Alonzo que serviam ao mesmo propósito que desenvolver uma máquina. Destas duas “máquinas”, a máquina de Turing é conceptualmente mais fácil de ensinar, então geralmente essa é a máquina que é ensinada em um curso de teoria computacional.
máquinas de Turing são pequenas e engraçadas máquinas teóricas que têm uma cabeça de leitura/escrita e uma fita de papel (hipotética) para a qual pode ler ou escrever. Baseado no que a máquina de Turing lê, ela coloca a máquina de Turing em um estado de ação que executa algum tipo de combinação de Tarefas consistindo em mover a leitura/escrita para frente ou para trás, lendo a partir de uma nova posição na fita, ou escrevendo assim uma nova posição na fita. Uma máquina de Turing é assim.:
Máquinas de Turing e Computadores Modernos
Uma coisa de interesse é que uma Máquina de Turing é, apesar de a superfície das aparências, na verdade, muito semelhante à de um computador moderno. Em um computador moderno, a unidade central de processamento (CPU) é equivalente à cabeça de leitura/escrita de uma máquina de Turing. Os chips de memória (RAM ou ROM) é muito semelhante às células da longa fita de papel que a máquina de tornear pode ler ou escrever. Então computadores modernos parecem ser aproximadamente equivalentes a uma máquina de Turing.
um computador moderno tem uma vantagem sobre a máquina de Turing. Um computador moderno não tem que se mover de uma célula de sua “memória” em ordem sequencial como uma máquina de Turing faz.
o fato de que uma máquina de Turing só pode mover uma célula de cada vez parece uma limitação significativa, não é? Acabamos de ver como algumas máquinas são logicamente “mais poderosas” do que outras: um PDA pode executar tarefas computacionais que uma FDA não pode. Então talvez haja máquinas que são mais poderosas do que máquinas de Turing que podem executar tarefas que Máquinas de Turing não podem? E talvez o computador moderno-devido à sua capacidade de saltar em torno da memória ao invés de ter que se mover de célula para célula sequencialmente — pode executar alguns programas que uma máquina de Turing não pode?
Na verdade moderno computador, na verdade, têm menos poder expressivo do que uma Máquina de Turing, em virtude do fato de que Máquinas de Turing foram concebidos como tendo um infinitamente longa fita de papel (i.e. infinito de memória) onde, como um computador, vai ter sempre finita de memória. No entanto, em geral, isso faz muito pouca diferença em que tipos de computações se pode realizar uma vez que os seres humanos não são geralmente todos os interessados em computações infinitamente longas que dão resultados infinitamente longos. É por isso que eu digo que computadores modernos e máquinas de Turing são “aproximadamente” equivalentes. Na verdade, desde que você assuma qualquer tamanho arbitrário mas finito de memória, eles são exatamente equivalentes em termos de que tipos de programas eles podem executar.
The Church Turing Thesis: Turing Machine = Max Logical Power
But what about poor Alonzo Church? Sua pobre “máquina” esquecida porque máquinas de Turing são mais fáceis de ensinar. Sua máquina talvez seja capaz de expressar alguns computações /programas que uma máquina de Turing não pode, ou vice-versa?Não seria uma coincidência estelar se acontecesse que Alan Turing e Alonzo Church criaram dois tipos completamente diferentes de máquinas de computação teórica e que eles eram exatamente idênticos em termos de que tipos de computação poderiam realizar?
Então, imagine a surpresa de todos quando Alan Turing foi capaz de produzir uma prova de que qualquer programa escrito para uma Máquina de Turing também pode ser escrito para uma Igreja máquina e também uma prova de que qualquer programa escrito para uma Igreja máquina também pode ser escrito para uma máquina de Turing.
na verdade, há uma série de tipos propostos de máquinas computacionais teóricas. Por exemplo, os teóricos tentaram permitir que uma máquina de Turing tivesse várias fitas para ler/escrever. Eles até tentaram permitir a uma máquina de Turing uma ‘folha’ bidimensional para ler e escrever. Os teóricos tentaram todos os tipos de melhorias para Máquinas de Turing (e máquinas de Igreja).
E até agora tem sido possível produzir uma prova para cada um deles que eles são equivalentes a uma simples Máquina de Turing.Isso parece uma coincidência, não parece? E seria uma coincidência selvagem a menos que haja um limite superior a que tipos de computação podem ser realizados.
Se existe um limite superior, então não seria coincidência que a Máquina de Turing e Church Máquina e todas as outras máquinas computacionais propostos acontecer de ter o mesmo poder computacional, pois na verdade, a razão pela qual eles são todos equivalentes, é porque chegamos ao limite superior do poder computacional.Mas podemos provar que não existe alguma máquina computacional por aí — uma que ainda não descobrimos — que tem a capacidade de realizar computações que uma máquina de Turing não pode?Como, exatamente, produziríamos tal prova? O fato é que não podemos provar que não há nada mais poderoso do que uma máquina de Turing. Então, quem sabe, talvez haja.
mas o fato é que não podemos encontrar (ou inventar) tais máquinas.
assim, após um esforço considerável tentando e falhando, para encontrar uma maneira de melhorar o poder das máquinas de Turing, finalmente a tese de Church-Turing foi aceita, mesmo que não tenha provado ser verdade. A tese de Church-Turing essencialmente diz algo assim.:
não É possível chegar com qualquer tipo de máquina computacional que pode executar um programa de lógica que uma simples Máquina de Turing não pode.
Ou, em outras palavras:
Máquinas de Turing e seus equivalentes são o mais eficiente possível tipos de máquinas computacionais e não há mais poderosos que nós simplesmente não sabemos sobre isso ainda.
After years and years of research on this Thesis, this Thesis still basically holds. Veremos mais tarde que houve alguma modificação na tese com a introdução de computadores quânticos teóricos. Mas, basicamente, a tese ainda é verdadeira hoje. Nunca ninguém encontrou uma maneira de superar as máquinas de Turing quando se trata de expressividade lógica. As máquinas de Turing ainda são as campeãs reinantes.Então agora você entende a tese de Church-Turing. No entanto, a tese de Church-Turing não é realmente equivalente ao princípio de Turing. Então em um post futuro vou desenvolver Qual é a diferença e quais são as ramificações filosóficas.
Notes
The Turing Principle. Assim nomeado por Roger Penrose, que não acredita nele (pelo menos não na forma atual). Foi desenvolvido no princípio Turing-Deutsch por David Deutsch, que acredita nele, pelo menos na sua forma.) (Ver artigo na Wikipédia para mais detalhes)