A interação é mais poderosa que os algoritmos?

17

Ouvi dizer que a interação do lema é mais poderosa que os algoritmos de Peter Wegner . A base da ideia é que uma Máquina de Turing (clássica) não pode lidar com interação, ou seja, comunicação (entrada / saída) com o mundo / ambiente externo.

Como isso pode ser assim? Como algo pode ser mais poderoso do que uma máquina de Turing? Qual é a essência dessa história? Por que não é mais conhecido?

Dave Clarke
fonte
1
Você tem uma referência para incluir em sua pergunta? Conheço a definição formal de uma Máquina de Turing, mas não sei exatamente o que você quer dizer com "interação".
Janoma
Além disso, parece que "não pode lidar com a interação com o ambiente" é semelhante a "não pode lidar com a aleatoriedade verdadeira", o que pode ser verdade, mas ambos podem ser bem aproximados com sensores e pseudo-aleatoriedade. Mas esse é um comentário desinformado, sem conhecer uma definição de interação.
Janoma
2
Máquinas de Turing não têm sensores.
21812 Dave Clarke
1
Estou ciente disso. E, no entanto, os computadores fazem usam sensores, que são uma forma particular de passar uma entrada para uma máquina de Turing. Então TMs fazer interagem com sinais externo / ambiente de alguma forma.
Janoma
2
A questão não é sobre computadores. A única interação com uma TM é que o ambiente fornece uma entrada para ela no início e recebe no máximo uma saída no final. Isso dificilmente é interação geral.
Dave Clarke

Respostas:

11

As máquinas de Turing podem lidar perfeitamente com a interação, usando fitas da Oracle. Funciona da seguinte forma: do ponto de vista de um computador que lida com a interação, a entrada do operador é simplesmente outra sequência de bits que é enviada ao computador de tempos em tempos. Todos sabemos que um sysadmin lento pode escrever um script para enviar a entrada para o programa quando solicitado, para que o sysadmin possa interromper mais cedo. A máquina de interação não tem como saber se existe realmente um operador ativo no console ou se a entrada está sendo canalizada de outro programa.

Ter toda a entrada de interação preparada antes do tempo é o mesmo, em termos teóricos, como ter toda a entrada em uma fita separada usada por uma máquina de Turing da Oracle. Sempre que o computador normalmente solicita interação do operador, a máquina lê da fita de entrada. Se a coisa lida na fita parecer inválida de alguma forma, a máquina de Turing fará exatamente o que a máquina de interação faria ao receber essa entrada.

Eu acho que Wagner está ciente da capacidade de usar fitas do oráculo para codificar a entrada, então você deve aceitar os comentários dele com um pouco de sal ou perguntar o que ele realmente quer dizer. Acredito que as pessoas que pensam em interação geralmente se preocupam com duas coisas:

  • Computadores "reais" têm interação, mas os algoritmos definidos por Turing não. Podemos contornar isso codificando a entrada em fitas Oracle, mas isso ainda não corresponde à maneira como computadores reais operam. Pode ser bom estudar modelos de computação mais alinhados com computadores reais.

  • Os algoritmos baseados em Oracle nem sempre são considerados na computação do dia-a-dia, porque os computadores normais não vêm com um "oráculo" mágico para fornecer dados. Mas podemos ser capazes de realmente usar apenas uma pessoa como oráculo. Se a pessoa entender os dados que estão sendo solicitados, poderá até ajudar o algoritmo, melhorando assim seu desempenho. Em outras palavras, um humano pode ser capaz de fornecer uma fita oráculo útil em vez de simplesmente uma aleatória, e, em princípio, isso pode levar a métodos de computação mais rápidos ou mais poderosos em comparação com os não baseados em oráculos. Afinal, acontece uma coisa com a computação aleatória, onde a máquina recebe uma sequência de bits aleatórios como uma entrada extra.

Carl Mummert
fonte
As fitas do Oracle não modelam corretamente a interação. Considere tentar provar que um sistema de computador não vaza informações particulares. Isso não pode ser formalizado em termos de uma TM com uma fita oracle fixa, porque a propriedade depende da caracterização do cálculo que o ambiente pode fazer - exatamente o que abstraímos com uma fita oracle.
Neel Krishnaswami
Depende do que você quer dizer com "modelar corretamente". Alguns trabalhos (por exemplo, da comunidade de hipercomputação) parecem sugerir que a interação de alguma forma amplia o conjunto de funções computáveis. O que faz, exatamente da mesma maneira que a computação oracle faz. Obviamente, você não pode usar TMs para estudar propriedades do ambiente de computação real; se você quiser saber se o processador do seu computador está com bugs, não ajudará a ignorá-lo completamente e basta olhar para as máquinas de Turing. Mas para perguntas que são apenas sobre a função que está sendo computada, interação e oráculos são equivalentes.
Carl Mummert
nn
Para um trabalho realmente completo dessa analogia, consulte Peter Hancock, Pierre Hyvernat: Interfaces de Programação e Topologia Básica. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.919
Neel Krishnaswami
1
n
8

Turning Machines modelam a computação e não têm um conceito de interação. Nesse sentido, uma máquina que suporta interação com um sistema externo pode fazer coisas que uma máquina de tornear não pode. Mas o cálculo feito entre bits de entrada de uma fonte externa obviamente sempre pode ser modelado por uma Máquina de Turing, portanto, mesmo uma "Máquina IO" não pode fazer nada com a entrada externa que uma Máquina de Turing não poderia fazer.

Em certo sentido, essa máquina pode "decidir" problemas indecidíveis pelas máquinas de Turing, mas apenas se você imaginar que o sistema com o qual está interagindo possui poderes de super-máquina de Turing e é confiável (de alguma forma; confiabilidade probabilística seria suficiente).

Imagine um programa para uma máquina IO como: "para qualquer entrada inicial da fita, imprima o conteúdo da fita e leia um símbolo da entrada externa; aceite se o símbolo for 1 e rejeite o contrário". Este programa pode decidir qualquer problema. Mas somente se o sistema externo com o qual ele pode interagir for capaz de decidir o problema; para mim, essa não é uma maneira muito interessante de dizer que a IO Machine of é capaz de decidir problemas indecidíveis pela Turing Machines.

Eu acho que sempre seria possível representar uma computação interativa imaginando uma máquina que recebe como entrada em sua fita uma codificação de alguma configuração anterior junto com uma entrada externa e faz com que a máquina pare com sua fita contendo uma codificação de uma configuração junto com saída. Então, o processo de "executar um programa" executa repetidamente esta Máquina de Turing de maneira mecânica, com a única parte "não mecânica" sendo, no entanto, a entrada externa é originada. Estou certo de que você poderia provar que, se um sistema desse tipo recebesse sua entrada, entregando sua saída a outra máquina de Turingconfigurado para operar de maneira semelhante, o sistema combinado possui poderes computacionais idênticos a uma única máquina de Turing. Acho que um argumento convincente de que a computação interativa não é mais poderosa que a computação não interativa, a menos que o sistema com o qual a computação interage seja mais poderoso que uma Máquina de Turing .


Há um sentido não teórico no qual a interatividade pode aumentar a capacidade de um computador para resolver problemas, no entanto. Há muitas coisas que os humanos fazem com muita precisão que não sabemos como fazer os computadores funcionarem muito bem. Mas também existem muitas coisas em que os humanos são péssimos, com os quais podemos conseguir computadores. A combinação desses dois pode levar a projetos como o reCaptcha , que efetivamente digitaliza automaticamente os livros, eliminando os problemas de reconhecimento de palavras para humanos em casos difíceis. O sistema resultante de trabalho computacional + humano alcança um resultado que atualmente é impraticável com o cálculo sozinho ou apenas o trabalho humano.

Ben
fonte
8

Recentemente, a ACM realizou o simpósio Ubiquity ' O que é computação? 'em que Peter Wegner publicou um artigo que reflete seus pontos de vista sobre computação interativa.

Aqui estão dois trechos do artigo de Peter Wegner:

Um novo conceito, ausente nas primeiras máquinas de Turing, é a "Computação Interativa", que acomoda a interação com o ambiente durante a computação.

As máquinas de interação podem executar formas de computação mais poderosas do que as máquinas de Turing e podem executar o tipo de pensamento proposto por Turing porque a interação melhora seu desempenho em relação ao das máquinas de Turing.

No entanto, Fortnow, que tem um artigo no mesmo simpósio, parece discordar das opiniões de Wegner e acredita que a computação interativa não oferece poder adicional sobre as Máquinas de Turing.

Para adicionar à mistura, parece que ainda estamos debatendo e definindo a computação. Moshe Vardi tem um artigo, O que é um algoritmo ?, Communications of the ACM, vol. 55, n. 3, março de 2012.

Vardi relata duas novas definições de algoritmos. O primeiro é proposto por Gurevich e o segundo por Moschovakis.

Gurevich argumentou que todo algoritmo pode ser definido em termos de uma máquina de estados abstratos.

Moschovakis, por outro lado, argumentou que um algoritmo é definido em termos de um recursor, que é uma descrição recursiva construída sobre operações arbitrárias tomadas como primitivas.

Mohammad Al-Turkistany
fonte
6

Não acho que os modelos com IO sejam "mais poderosos" que as máquinas de Turing, apenas modelam coisas diferentes.

Em teoria, você poderia ver IO como oráculo (barulhento?). Com um oráculo perfeito, você pode computar funções não-computáveis ​​de Turing; mas de onde conseguir o oráculo? Os humanos são a única opção "super-Turing" (se houver) e somos conhecidos por não sermos confiáveis.

Uma classe de programas que se encaixa nesse modelo são assistentes interativos de prova (por exemplo, Isabelle / HOL , Coq ). Eles lidam com espaços de prova indecidíveis, mas (sem dúvida) todas as provas podem ser encontradas (e verificadas) com a entrada adequada do usuário.

Rafael
fonte
Portanto, as Máquinas de Turing com Oracles são mais poderosas que as Máquinas de Turing sem eles e as Máquinas de Turing com Oracles podem modelar a interação. Então a resposta parece ser sim.
21412 Dave Clarke
1
@DaveClarke Se você considera oráculos perfeitos, sim.
Raphael
2
Penso que uma máquina (ou programa) não assistida (por qualquer forma de oráculo ou entrada) poderia, em princípio, encontrar todas as provas. Existem dois problemas: (1, teórico): nunca será capaz de verificar que uma afirmação não tem prova e (2, prático): gerar provas cegamente na esperança de tropeçar em uma determinada afirmação é tão terrivelmente ineficiente que ninguém quer tentar e, assim, os assistentes de prova preferem uma pesquisa guiada, abandonando o sucesso "garantido" caso exista uma prova.
Marc van Leeuwen
2
Como Ben aponta em sua resposta, a maneira correta de olhar para ela não é "máquinas de Turing com oráculos são mais poderosas"; as próprias máquinas estão apenas fazendo coisas computáveis. A maneira correta de ver isso é "alguns oráculos não são computáveis ​​e, a partir desses oráculos, podemos calcular coisas que não podemos computar sem um oráculo". A força computacional vem do oráculo, e não da máquina.
Carl Mummert
Parece que as máquinas de Turing com oráculos são a coisa mais poderosa. Por que se preocupar com novas definições?
saadtaame