Uma máquina de Turing “por definição” é a máquina mais poderosa?

54

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?

Sounak Bhattacharya
fonte
9
A máquina de torneamento não pode resolver o problema da parada. No entanto, não há provas de que não há máquina para resolvê-lo. O modelo é uma espécie de TM com oracle, ou abordagem completamente diferente. Se você segue a tese da Igreja, a TM representa apenas máquinas que estamos usando hoje em dia.
Eugene
16
É a máquina mais poderosa que sabemos construir . Bem, na verdade não, só podemos construir autômatos finitos.
Raphael
13
Seu problema é que você pensa nas MTs como algo que veio depois. Não era. Foi (e é) usado para definir a classe de problemas computáveis de Turing . Muitos modelos equivalentes foram encontrados, mas isso não altera a definição.
Raphael
3
Existem centenas de arquiteturas de computadores diferentes (completas de Turing) por aí, todas com conjuntos de instruções muito diferentes. Eu não acho que é óbvio a todos que não há nenhum problema que se pode resolver, mas outro não pode.
BlueRaja - Danny Pflughoeft
5
... o que você está dizendo simplesmente não é a tese de Church-Turing ? Até onde sabemos, ninguém refutou a tese, mas não podemos excluir a existência de um modelo diferente de computação que seja "razoável" (isto é, de alguma forma implementável) e mais forte que as TMs.
Bakuriu

Respostas:

135

Concordo que uma máquina de Turing pode fazer "todos os possíveis problemas matemáticos".

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 ).

A Turing Machine é "por definição" a máquina mais poderosa?

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.

Qual é a novidade que Alan Turing nos deu?

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 é .

David Richerby
fonte
3
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
DW
Você não quer dizer soluções racionais? Eu acho que soluções inteiras são possíveis em um número finito de etapas.
Trenin
2
@Trenin A página da Wikipedia que eu vinculo diz "número inteiro racional", que explica ser uma frase usada algumas vezes para distinguir números inteiros comuns de objetos como números Gaussianos (números complexos onde ). a , b Za+iba,bZ
David Richerby
Entendi. Além disso, o que eu pensava ser possível acaba sendo muito mais difícil do que eu pensava.
Trenin
64

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 ?

Andrej Bauer
fonte
19
"Você precisa imaginar uma época em que a palavra" computador "significasse uma pessoa, não uma máquina". Este é um lembrete realmente útil. Em essência, Turing tentou simular efetivamente, com sua "máquina", as operações que uma pessoa poderia realizar com caneta e papel naquele momento para calcular algo.
Sorrop 01/12/16
2
"Seu teorema sobre a existência de máquinas universais foi a invenção do computador moderno de uso geral". - Bem ... no mundo matemático, talvez. Pessoas como Konrad Zuse desenvolveram computadores de uso geral de forma independente.
Raphael
6
@AndrejBauer Isso ainda sugere uma linha do tempo e uma dependência que não existiam, nem em todos os casos. Não culpo você - poucas pessoas sabem o que Zuse fez quando. O fato é que ele construiu computadores desde 1935 durante a Segunda Guerra Mundial, sem muita ou nenhuma contribuição de fora da Alemanha. Ele também desenvolveu seu Plankalkül durante esse período. Eu acho que foi com os computadores como com muitas outras coisas: o tempo estava maduro, muitas mentes pensavam da mesma maneira. A propósito, apesar de todas as suas contribuições, Turing não inventou a computação .
Raphael
12
@ Rafael: Konrad Zuse não sabia que sua máquina pode processar todos os problemas computáveis ​​(agora sabemos que suas máquinas ESTÃO Turing completas - memória de módulo). O que Turing contribuiu NÃO foi a idéia de que as máquinas podem fazer cálculos - Babbage fez isso antes de Zuse ou Turing. O que Turing contribuiu foi a ideia de que conjuntos de instruções e linguagens de programação não importam realmente na teoria. Esta não é uma ideia óbvia. Ironicamente, é essa ideia de que impulsiona o desenvolvimento de CPUs e linguagens de programação
slebetman
11
"conjuntos de instruções e linguagens de programação realmente não importam na teoria" - isso é claramente falso. As diferenças podem importar, mas nem sempre. Turing definiu um determinado modelo de computação e afirmou que era o mais poderoso possível. Preso entre a advertência da memória infinita e os modelos mais poderosos, não tenho muita certeza de que essa afirmação retenha água. Então, de certa forma, ele não fez nada além de Zuse, se com matemática, em vez de metal.
Raphael
23

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.

André Souza Lemos
fonte
11
Mas qualquer coisa solucionável deve ser resolvida por um "processo" (por definição). Talvez não conheçamos o processo para resolver um problema "solucionável" específico no momento. Nesse caso, significa que o problema é solucionável, mas não pode ser resolvido agora. Isso não significa efetivamente que "qualquer coisa que possa ser solucionada pode ser representada por um algoritmo" porque "process" = "algoritmo". Por que você diz que não é óbvio?
Sounak Bhattacharya
13
O que é um "processo"? Veja, é fácil rodar em círculos, substituindo um conceito pouco claro por outro. A tentativa de Turing foi na verdade um experimento mental encarnado, que ainda alimenta nossa imaginação, até hoje. Isso não é uma coisa pequena.
André Souza Lemos
@SounakBhattacharya Por algum processo (de anos e genialidade), Sir Andrew Wiles provou que o Último Teorema de Fermat era verdadeiro. Você imagina que existe uma TM que poderia ter feito essa determinação?
OJFord 01/12/16
11
@OllieFord Bem, se a prova for suficientemente rigorosa para que cada etapa possa ser expressa em termos de axiomas bem especificados existentes, a prova poderá ser verificada por uma máquina de Turing. Poderíamos então especificar uma máquina de Turing que enumere todas as provas possíveis e certamente (mas muito lentamente) a máquina encontraria essa prova. Uma implementação física simples dessa máquina de Turing levaria mais de 400 anos e muito mais do que a vida útil esperada do universo.
gmatht
19

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)

As máquinas de Turing são dispositivos teóricos, mas foram projetadas tendo em vista as limitações físicas. Em particular, incorporamos em nosso modelo restrições provenientes de:

  • (a) ATOMISMO, garantindo que a quantidade de informação que pode ser codificada em qualquer configuração da máquina (como um sistema finito) seja limitada; e

  • (b) RELATIVIDADE, excluindo ações à distância e fazendo com que o efeito causal se propague por meio de interações locais. Gandy [1980] mostrou que a noção de máquina de Turing é suficientemente geral para incluir, em um sentido preciso, qualquer dispositivo de computação que satisfaça limitações semelhantes.

e na p. 107: (Uma teoria geral de dispositivos determinísticos discretos)

A análise (Church [1957], Kolmogorov e Uspenskii [1958], Gandy [1980]) parte dos pressupostos do atomismo e da relatividade. O primeiro reduz a estrutura da matéria a um conjunto finito de partículas básicas de dimensões limitadas e, assim, justifica a possibilidade teórica de desmontar uma máquina até um conjunto de constituintes básicos. Este último impõe um limite superior (a velocidade da luz) à velocidade de propagação de mudanças causais e, assim, justifica a possibilidade teórica de reduzir o efeito causal produzido em um instante t em uma região delimitada do espaço V, às ações produzidas pelas regiões cujos pontos estão a uma distância c * t de algum ponto V. É claro que as suposições não levam em conta sistemas que são contínuos ou que permitem ação à distância ilimitada (como os sistemas gravitacionais newtonianos).

A análise de Gandy mostra que O COMPORTAMENTO É RECORRENTE, PARA QUALQUER DISPOSITIVO COM UM LIMITE FIXO NA COMPLEXIDADE DE SUAS CONFIGURAÇÕES POSSÍVEIS (no sentido de que ambos os níveis de formação conceitual dos constituintes e o número de constituintes em qualquer parte estruturada do qualquer configuração, são delimitadas) E CONJUNTOS DE INSTRUÇÕES FINITAS E DETERMINÍSTICAS FIXAS PARA AÇÃO LOCAL E GLOBAL (a primeira diz como determinar o efeito de uma ação em partes estruturadas e a segunda como reunir os efeitos locais). Além disso, a análise é ótima no sentido de que, quando tornada precisa, qualquer relaxamento das condições se torna compatível com qualquer comportamento e, portanto, fornece uma descrição suficiente e necessária do comportamento recursivo.

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)

Bill Dubuque
fonte
2
Muito obrigado! Sempre achei que as máquinas de Turing eram estranhamente deselegantes, mas isso explica bastante por que isso pode ser mal interpretado.
PJTraill
6

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.

James Brock
fonte
2
Depois que "super-duper-pooper" vem "super-duper-ooper-flooper", ou pelo menos é disso que me lembro quando tinha 7 ou 8 anos. É provavelmente a terminologia formal correta.
6606 Peter Cordes
4

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".

Adam Gawne-Cain
fonte
3
Bem vindo ao site! "Mais poderoso" no contexto da teoria da computação é geralmente considerado como "capaz de calcular mais funções", em vez de "capaz de calcular em menos etapas", então não tenho certeza se o seu (a) realmente conta. Além disso, não está claro como um computador poderia usar valores reais. Como você introduziria um valor real que não era, digamos, um real computável? Como você diria a outra pessoa qual o valor que ela deveria inserir em sua máquina contínua e como você lidaria com o ruído? Mas talvez essa seja uma objeção tola como "Como você produziria fita suficiente para a máquina de Turing usar".
precisa saber é o seguinte
-4

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.

gnasher729
fonte
12
Você poderia esclarecer como isso responde à pergunta?
precisa saber é o seguinte
11
Obviamente, uma verdadeira máquina de Turing seria capaz de processar fotos e vídeos. É claro que algum tipo de dispositivo de saída de imagem seria necessário para os humanos vê-los, mas isso se aplica a qualquer computador; uma CPU + memória em uma placa de circuito também não é "de nenhuma utilidade para isso".
Hyde
11
Entre os modelos de máquinas com memória infinita, as TMs não são as mais poderosas!
Raphael