Concordo que uma máquina de Turing pode fazer "todos os possíveis problemas matemáticos". Mas isso é porque é apenas uma representação de máquina de um algoritmo: primeiro faça isso, depois faça aquilo, finalmente produza isso.
Quero dizer que qualquer coisa solucionável pode ser representada por um algoritmo (porque essa é precisamente a definição de 'solucionável'). É apenas uma tautologia. Eu não disse nada de novo aqui.
E ao criar uma representação de máquina de um algoritmo, que ele também resolverá todos os problemas possíveis também não é novidade. Isso também é mera tautologia. Então, basicamente, quando se diz que uma máquina de Turing é a máquina mais poderosa, o que efetivamente significa é que a máquina mais poderosa é a máquina mais poderosa!
Definição de "mais poderoso": aquilo que pode aceitar qualquer idioma.
Definição de "Algoritmo": Processo para fazer qualquer coisa. Representação de máquina do "Algoritmo": Uma máquina que pode fazer qualquer coisa.
Portanto, é lógico que a representação da máquina de um algoritmo seja a máquina mais poderosa. Qual é a novidade que Alan Turing nos deu?
fonte
Respostas:
Bem, você não deveria, porque não é verdade. Por exemplo, as máquinas de Turing não podem determinar se polinômios com coeficientes inteiros têm soluções inteiras ( décimo problema de Hilbert ).
Não. Podemos sonhar com uma hierarquia infinita de máquinas mais poderosas . No entanto, a máquina de Turing é a máquina mais poderosa que sabemos, pelo menos em princípio, como construir. Porém, isso não é uma definição: é apenas que não temos idéia de como construir algo mais poderoso, ou se é possível.
Uma definição formal de algoritmo. Sem essa definição (por exemplo, a máquina de Turing), temos apenas definições informais de algoritmo, de acordo com as linhas de "Um procedimento finitamente especificado para resolver algo". OK ótimo. Mas que medidas individuais esses procedimentos podem tomar?
As etapas das operações aritméticas básicas são? Encontrar o gradiente de uma curva é um passo? Encontrar raízes de polinômios é um passo? Encontrar raízes inteiras de polinômios é um passo? Cada um desses parece tão natural. No entanto, se você permitir todos eles, seus "procedimentos finitamente especificados" são mais poderosos que as máquinas de Turing, o que significa que elas podem resolver coisas que não podem ser resolvidas por algoritmos. Se você permitir tudo, exceto o último, ainda estará nos reinos da computação de Turing.
Se não tivéssemos uma definição formal de algoritmo, nem conseguiríamos fazer essas perguntas. Nós não seria capaz de discutir o que algoritmos podem fazer, porque não saberia o que um algoritmo é .
fonte
Você não está correto quando faz repetidamente declarações sobre isso ou aquilo ser "apenas uma tautologia". Então, permita-me colocar suas reivindicações em um pouco de contexto histórico.
Primeiro de tudo, você precisa tornar os conceitos que você usa precisos. O que é um problema? O que é um algoritmo? O que é uma máquina? Você pode pensar que isso é óbvio, mas boa parte das décadas de 1920 e 1930 foi gasta por lógicos tentando entender essas coisas. Havia várias propostas, uma das quais eram as máquinas de Turing, as mais bem-sucedidas. Mais tarde, descobriu-se que as outras propostas eram equivalentes às máquinas de Turing. Você deve imaginar uma época em que a palavra "computador" significasse uma pessoa, não uma máquina. Você está apenas surfando a onda e as consequências das brilhantes invenções de mentes brilhantes de cem anos atrás, sem estar ciente disso.
As máquinas de Turing são descritas concretamente em termos de estados, cabeça e fita de trabalho. Está longe de ser óbvio que isso esgota as possibilidades computacionais do universo em que vivemos. Não poderíamos fazer uma máquina mais poderosa usando eletricidade, água ou fenômenos quânticos? E se colocarmos uma máquina de Turing em um buraco negro na velocidade e direção certas, para que ela possa executar infinitamente muitos passos no que nos parece um tempo finito? Você não pode simplesmente dizer "obviamente não" - você precisa primeiro fazer alguns cálculos na relatividade geral. E se os físicos descobrirem uma maneira de se comunicar e controlar universos paralelos, para que possamos rodar infinitamente muitas máquinas de Turing em tempo paralelo?
Ele não importa o que, neste momento não podemos fazer essas coisas. O importante, no entanto, é que você entenda que Turing teve que pensar no que era fisicamente possível (com base no conhecimento da física da época). Ele não escreveu apenas "uma mera tautologia". Longe disso, ele analisou cuidadosamente o que a computação significa em um sentido informal, depois propôs um modelo formal, argumentou com muito cuidado que esse modelo captura o que as pessoas entendiam por "computação", e derivou alguns teoremas importantes sobre isso. Um desses teoremas diz que as máquinas de Turing não podem resolver todos os problemas matemáticos (ao contrário de uma de suas falsas afirmações). Tudo isso, em um único artigo, escrito durante a vacinação no verão, enquanto ele era estudante.foi a invenção da idéia do computador moderno de uso geral. Depois disso, era apenas uma simples questão de engenharia.
Isso responde ao que Turing contribuiu para a humanidade além de uma mera tautologia? E você realmente leu o jornal dele ?
fonte
Que "qualquer coisa que possa ser resolvida pode ser representada por um algoritmo" não é óbvio.
Esse tem sido objeto de intenso debate, já que Alan Turing, reformulando as idéias da Igreja Alonzo, propôs uma definição de números computáveis que assumiam a forma da máquina a que você está se referindo. É importante ressaltar que essas não eram as únicas pessoas que trabalhavam nesse tipo de coisa naquela época.
Ainda o chamamos de tese - ou conjectura - já que "qualquer coisa que possa ser calculada" claramente não é um objeto matemático preciso, cuja estrutura e alcance poderiam ser estudados de maneira não especulativa.
fonte
Primeiro, é importante ter em mente que as Máquinas de Turing foram inicialmente concebidas por Turing não como um modelo de qualquer tipo de computador fisicamente realizável, mas como um limite ideal para o que é computável por um humano calculando em um processo mecânico passo a passo. (sem qualquer uso de intuição). Este ponto é amplamente incompreendido - veja [1] para uma excelente exposição sobre este e outros tópicos relacionados.
As limitações de finitude postuladas por Turing para suas Máquinas de Turing são baseadas em limitações postuladas do aparelho sensorial humano. As generalizações das análises de Turing para dispositivos de computação fisicamente realizáveis (e teses análogas de Church-Turing) não vieram até muito mais tarde (1980) devido a Robin Gandy - com limitações baseadas nas leis da física. Como Odifreddi diz na p. 51 de [2] (bíblia da teoria clássica da recursão)
e na p. 107: (Uma teoria geral de dispositivos determinísticos discretos)
A análise de Gandy fornece uma perspectiva muito esclarecedora sobre o poder e as limitações das máquinas de Turing. Vale a pena ler para obter mais informações sobre esses assuntos. Esteja avisado, no entanto, que o artigo de Gandy de 1980 [3] é considerado difícil, mesmo por alguns conhecedores. Você pode achar útil examinar primeiro os artigos em [4], de J. Shepherdson e A. Makowsky.
[1] Sieg, Wilfried. Procedimentos mecânicos e experiência matemática. [pp. 71-117 em Matemática e mente. Trabalhos da Conferência sobre Filosofia da Matemática, realizada no Amherst College, Amherst, Massachusetts, de 5 a 7 de abril de 1991. Editado por Alexander George. Computação Lógica. Philos., Oxford Univ. Press, Nova York, 1994. ISBN: 0-19-507929-9 MR 96m: 00006 (Revisor: Stewart Shapiro) 00A30 (01A60 03A05 03D20)
[2] Odifreddi, Piergiorgio. Teoria da recursão clássica. A teoria das funções e conjuntos de números naturais. Com um prefácio da GE Sacks. Estudos em lógica e os fundamentos da matemática, 125. North-Holland Publishing Co., Amsterdã-Nova York, 1989. xviii + 668 pp. ISBN: 0-444-87295-7 MR 90d: 03072 (Revisor: Rodney G. Downey ) 03Dxx (03-02 03E15 03E45 03F30 68Q05)
[3] Gandy, Robin. Tese e princípios da Igreja para mecanismos. Simpósio Kleene. Anais do Simpósio realizado na Universidade de Wisconsin, Madison, Wisconsin, 18 a 24 de junho de 1978. Editado por Jon Barwise, H. Jerome Keisler e Kenneth Kunen. Estudos em Lógica e os Fundamentos da Matemática, 101. North-Holland Publishing Co., Amsterdã-Nova York, 1980. xx + 425 pp. ISBN: 0-444-85345-6 MR 82h: 03036 (Revisor: Douglas Cenzer) 03D10 (03A05)
[4] A máquina universal de Turing: uma pesquisa de meio século. Segunda edição. Editado por Rolf Herken. Computercultur [Computer Culture], II. Springer-Verlag, Viena, 1995. xvi + 611 pp. ISBN: 3-211-82637-8 MR 96j: 03005 03-06 (01A60 03D10 03D15 68-06)
fonte
A melhor discussão popular sobre essa questão que eu já li é o ensaio de Scott Aaronson, professor do MIT, Quem pode nomear o número maior? , em que ele explora, entre outras coisas, as implicações das máquinas super-Turing, máquinas super-duper-Turing e máquinas super-duper-pooper-Turing.
fonte
Não, as TMs não são mais poderosas. Dois exemplos:
a) Pode haver outras máquinas que calculam os mesmos resultados que uma MT, mas algoritmicamente mais rápidas (por exemplo, computadores quânticos computando fatores primos). "Mais rápido" é um tipo de poder.
b) TMs não podem representar números reais em geral com precisão perfeita. Mas um computador analógico (CA) pode ser capaz de representar e fazer aritmética com números reais com precisão perfeita. Isso seria mais poderoso do que qualquer TM.
É claro que (b) exige que o nosso universo tenha algumas propriedades contínuas (gravidade?) Que a CA pode usar para representar valores reais. Talvez todas as propriedades físicas, incluindo a gravidade, sejam quantizadas. Mas podemos especular sobre máquinas em um universo contínuo. Portanto, as TMs não são mais poderosas "por definição".
fonte
Se você observar a complexidade computacional, uma máquina de Turing é a máquina mais poderosa - porque possui memória ilimitada e nenhuma máquina real possui. Qualquer máquina real não pode resolver problemas de tamanho arbitrário; eles nem conseguem ler um problema, muito menos resolvê-lo.
Por outro lado, se você tentar implementar uma máquina de Turing real, digamos que ela pare e toque um alarme se ficar sem fita, você descobriria que seriam necessárias muito mais etapas para realizar qualquer tipo de cálculo do que digamos a máquina real em um telefone barato, e seria muito mais lento na solução de problemas reais. Você também descobriria que escrever uma resposta em uma fita não é uma interface de usuário muito boa. E você descobriria que muitas pessoas usam computadores não para resolver problemas, mas para enviar fotos de nus para seus amigos e para assistir a vídeos de gatos, e uma Máquina de Turing não serve para nada disso.
fonte