Aplicabilidade da tese de Church-Turing a modelos interativos de computação

Paul Wegner e Dina Goldin publicam há mais de uma década artigos e livros, argumentando principalmente que a tese de Church-Turing é frequentemente deturpada na comunidade da Teoria da CS e em outros lugares. Ou seja, é apresentado como abrangendo todo o cálculo quando, de fato, se aplica apenas ao cálculo de funções, que é um subconjunto muito pequeno de todo o cálculo. Em vez disso, eles sugerem que devemos procurar modelar a computação interativa, onde a comunicação com o mundo exterior acontece durante a computação.

A única crítica que vi deste trabalho está no fórum Lambda the Ultimate , onde alguém lamentou esses autores por publicar continuamente o que é obviamente conhecido. Minha pergunta então é: existe mais crítica nessa linha de pensamento e, em particular, em suas Máquinas de Turing Persistentes. E, se não, por que, então, parece ser muito pouco estudado (eu poderia estar enganado). Por fim, como a noção de universalidade se traduz em um domínio interativo.

Aqui está a minha analogia favorita. Suponha que passei uma década publicando livros e documentos argumentando que, ao contrário do dogma teórico da ciência da computação, a Tese de Church-Turing falha em capturar toda a computação, porque as máquinas de Turing não conseguem brindar pão . Portanto, você precisa do meu novo modelo revolucionário , a TETM (Toaster-Enhanced Turing Machine), que permite o pão como uma entrada possível e inclui tostá-lo como uma operação primitiva.

Você pode dizer: claro, eu tenho um "ponto", mas é totalmente desinteressante. Ninguém jamais afirmou que uma máquina de Turing poderia lidar com todas as interações possíveis com o mundo externo, sem antes conectá-la a periféricos adequados. Se você deseja que uma TM brinde pão, é necessário conectá-lo a uma torradeira; então a TM pode lidar facilmente com a lógica interna da torradeira (a menos que essa torradeira em particular exija a solução do problema de parada ou algo parecido para determinar o quão marrom o pão deve ficar!). Exatamente da mesma maneira, se você deseja que uma TM manipule a comunicação interativa, é necessário conectá-la a dispositivos de comunicação adequados, como Neel discutiu em sua resposta. Em nenhum dos casos, estamos dizendo algo que não seria óbvio para o próprio Turing.

Então, eu diria que a razão pela qual não houve "acompanhamento" das diatribes de Wegner e Goldin é que o TCS sabe modelar a interatividade sempre que necessário, e o faz feliz, desde o início do campo.

Atualização (30/8): Um ponto relacionado é o seguinte. Será que alguma vez os críticos fazem uma pausa de que, aqui dentro da Torre de Marfim de Elite Church-Turing (ECTIT), os principais temas de pesquisa das duas últimas décadas incluem provas interativas, protocolos criptográficos multipartidários, códigos para comunicação interativa, protocolos assíncronos para roteamento , consenso, divulgação de boatos, eleição de líderes etc. e o preço da anarquia nas redes econômicas? Se colocar a noção de computação de Turing no centro do campo torna tão difícil discutir a interação, como é que tão poucos de nós notamos?

Outra atualização: para as pessoas que continuam batendo o tambor sobre os formalismos de nível superior serem muito mais intuitivos que as TMs, e ninguém pensando em termos de TMs como uma questão prática, deixe-me fazer uma pergunta extremamente simples. O que permite que todas essas linguagens de alto nível existam , para garantir que elas sempre possam ser compiladas no código da máquina? Poderia ser ... err ... A TESTE DA IGREJA DA IGREJA , a mesma em que você está falando mal ? Para esclarecer, a Tese de Church-Turing não é a afirmação de que "TURING MACHINEZ ORDEM !!" Pelo contrário, é a alegação de que qualquer linguagem de programação razoável será equivalente em potência expressiva às máquinas de Turing - e, como conseqüência, que você também pode pensar em termos dos idiomas de nível superior, se for mais conveniente fazê-lo. Esta, é claro, foi uma nova e radical visão 60-75 anos atrás.

Atualização final: criei uma postagem no blog para uma discussão mais aprofundada sobre esta resposta.

Eu acho que a questão é bastante simples.

1. Todos os formalismos interativos podem ser simulados pelas máquinas de Turing.

2. As TMs são linguagens inconvenientes para pesquisas em computação interativa (na maioria dos casos), porque as questões interessantes são abafadas pelo barulho das codificações.

3. Todo mundo que trabalha na matematização da interação sabe disso.

Deixe-me explicar isso em mais detalhes.

As máquinas de Turing podem obviamente modelar todos os modelos interativos de computação existentes no seguinte sentido: Escolha alguma codificação da sintaxe relevante como cadeias binárias, escreva uma TM que tome como entrada dois programas interativos codificados P, Q (em um modelo escolhido de computação interativa) e retorna verdadeiro exatamente quando há uma redução em uma etapa de P para Q no sistema de reescrita de termos relevante (se o seu cálculo tiver uma relação de transição ternária, prossiga mutatis mutandis). Então você tem uma TM que faz uma simulação passo a passo da computação no cálculo interativo. Claramente o cálculo pi, o cálculo ambiental, o CCS, o CSP, as redes de Petri, o cálculo pi temporizado e qualquer outro modelo interativo de computação estudado podem ser expressos nesse sentido. É isso que as pessoas querem dizer quando dizem que a interação não vai além das MTs.

N. Krishnaswami refere-se a uma segunda abordagem para modelar a interatividade usando fitas de oráculo. Essa abordagem é diferente da interpretação da relação de redução / transição acima, porque a noção de MT é alterada: passamos de MTs simples para MTs com fitas oracle. Essa abordagem é popular na teoria da complexidade e criptografia, principalmente porque permite que pesquisadores dessas áreas transfiram suas ferramentas e resultados do mundo seqüencial para o mundo concorrente.

O problema com ambas as abordagens é que as questões teóricas da concorrência genuinamente são obscurecidas. A teoria da concorrência busca entender a interação como um fenômeno sui generis. Ambas as abordagens via TMs simplesmente substituem um formalismo conveniente para expressar uma linguagem de programação interativa por um formalismo menos conveniente.

Em nenhuma das abordagens, questões teóricas de concorrência genuína, ou seja, a comunicação e sua infraestrutura de suporte têm uma representação direta. Eles estão lá, visíveis aos olhos treinados, mas codificados, ocultos no nevoeiro impenetrável da complexidade da codificação. Portanto, ambas as abordagens são ruins na matematização das principais preocupações da computação interativa. Tomemos, por exemplo, qual poderia ser a melhor idéia na teoria das linguagens de programação no último meio século, a axiomatização da extrusão de escopo de Milner et al (que é um passo fundamental em uma teoria geral da composicionalidade):

Quão lindamente simples é essa idéia quando expressa em uma linguagem de linguagem personalizada, como o pi-calculus. Fazer isso usando a codificação do pi-calculus nas TMs provavelmente preencheria 20 páginas.

Em outras palavras, a invenção de formalismos explícitos para a interação deu a seguinte contribuição à ciência da computação: a axiomatização direta das principais primitivas da comunicação (por exemplo, operadores de entrada e saída) e os mecanismos de apoio (por exemplo, nova geração de nomes, composição paralela etc.) . Essa axiomatização se transformou em uma verdadeira tradição de pesquisa com suas próprias conferências, escolas e terminologia.

Uma situação semelhante ocorre em matemática: a maioria dos conceitos pode ser escrita usando a linguagem da teoria dos conjuntos (ou teoria dos topos), mas preferimos conceitos de nível superior, como grupos, anéis, espaços topológicos e assim por diante.

$\mathbb{N} \to \mathbb{N}$

No entanto, ainda é verdade que as máquinas de Turing são bastante dolorosas para modelar propriedades como interatividade. O motivo é um pouco sutil e tem a ver com os tipos de perguntas que queremos fazer sobre cálculos interativos.

A primeira passagem usual na modelagem da interação com as TMs é com fitas da Oracle. Intuitivamente, você pode pensar na sequência impressa na fita oracle como sendo uma "previsão" da interação de E / S da máquina de Turing com o ambiente. No entanto, considere os tipos de perguntas que queremos fazer sobre programas interativos: por exemplo, podemos querer saber que um programa de computador não produzirá seus dados financeiros, a menos que receba seu nome de usuário e senha como entrada e, além disso, que os programas não vazem informações sobre senhas. Falar sobre esse tipo de restrição é muito doloroso com as cordas do oráculo, pois reflete uma restrição epistêmica temporal no traço da interação, e a definição das fitas do oráculo pede que você forneça toda a corda na frente.

Eu suspeito que acertar é factível e equivale essencialmente a (1) considerar as cordas do oráculo não como um conjunto, mas como um espaço topológico cujos conjuntos abertos codificam a lógica modal de tempo e conhecimento que você deseja modelar e (2) garantir que os teoremas que você prova são todos contínuos com relação a essa topologia, visualizando os predicados como funções contínuas, desde cadeias de oráculos até valores de verdade vistos como o espaço de Sierpinski. Devo enfatizar que isso é um palpite , baseado na analogia com a teoria de domínio. Você precisaria elaborar os detalhes (e provavelmente enviá-los ao LICS ou algo assim) para ter certeza.

Como resultado, as pessoas preferem modelar a interação usando coisas como o modelo Dolev-Yao , em que você modela explicitamente a interação entre computadores e o ambiente, para poder caracterizar explicitamente o que o invasor sabe. Isso facilita muito a formulação de lógicas modais apropriadas para raciocinar sobre segurança, uma vez que o estado do sistema e o estado do ambiente são representados explicitamente.

lendo o blog Lance Fortnows, acabei de ler este artigo de pesquisa recente / agradável / longo sobre o assunto, com muitas perspectivas e referências [1] (que não foi citado até agora), inclui a perspectiva de Wegner / Goldin (entre muitas outras). Apenas cito Fortnows excelente / enfático resumo / declaração / afirmação da linha do partido TCS quase oficial / uniforme / unânime:

"Alguns cientistas da computação, no entanto, tentam argumentar que a tese [de Church-Turing] falha em capturar alguns aspectos da computação. Alguns deles foram publicados em locais de prestígio, como Science, Communications of the ACM, e agora como toda uma série de artigos na ACM Ubiquity. Algumas pessoas fora da ciência da computação podem pensar que há um sério debate sobre a natureza da computação. Não existe. "

[1] Turing Titanic Machine por Barry S Cooper CACM, vol. 55

Estou muito de acordo com os comentários de Aaronson.

Não entendo o trabalho de Milner. (por exemplo, cálculo pi, que Milner inventou para descrever processos de comunicação). É bastante ilegível para mim, assim como quase todos os trabalhos sobre matemática e lógica, como as teorias de Lambek. Não tenho dúvidas de que as idéias de Lambek são muito boas, mas gostaria de vê-las traduzidas para algum tipo de inglês pidgin que eu possa ler.

Fico impressionado com o comentário de Milner de que o cálculo lambda é bom para "processos sequenciais", mas que algo mais é necessário para os processos de comunicação.

Meu ponto de vista (talvez ingênuo) foi que não pode ser assim, porque o cálculo pi é Turing completo e, portanto, pode ser convertido mecanicamente em outra notação de Turing completa, ou seja, cálculo lambda. Portanto, a notação de cálculo pi de Milner pode ser convertida automaticamente em cálculo lambda.

Parece que identifiquei um projeto: intuitivamente, deveria ser possível converter mecanicamente de uma linguagem completa de Turing para outra. existe um algoritmo para fazer isso? Vou ter que procurar no Google. Talvez isso seja incrivelmente difícil de fazer e tão difícil quanto o problema da parada.

Procurei ontem na net e encontrei documentos sobre modelos de cálculo lambda. Fiquei surpreso ao descobrir que isso parece ser uma toca de coelho muito profunda.

Richard Mullins

A questão é que, depois de adicionar interatividade (pura), a formalidade sai pela janela. Não é mais um sistema "fechado". A questão então é: qual é a noção de computação depois que a interatividade entra? Essa resposta: bem, ou o outro usuário / máquina está substituindo parte de sua computação (que pode ser solicitada por apenas outra máquina de estado maior) ou você não está mais em um sistema formalmente definido e agora está jogando um jogo , caso em que não há aplicação da tese de Church-Turing.

folheando o jornal de Wegner, fica claro que ele está sendo um pouco melodramático e contrário, mas ele tem razão. o futuro da computação é indiscutivelmente muito mais centrado na robótica , IA ou datamining (do vasto "big data" do mundo real) que ele não parece mencionar muito pelo nome, mas que ele está claramente aludindo ao seu modelo. e essas áreas concentram-se amplamente no universo fora das entradas e saídas de uma TM.

historicamente, também recebeu o nome de cibernética, conforme inventado / formulado por Weiner. o objetivo da robótica é que entradas e saídas não são meramente digitais e sem significado, o que se pode concluir olhando para uma MT; são, mas têm implicações / efeitos / causas no mundo real, etc., e a máquina forma um ciclo de feedback com o ambiente.

então eu diria que as MTs e a robótica formam uma sinergia muito natural ou uma relação simbiótica, por assim dizer. mas isso não é uma afirmação radical e o que Wegner anuncia com grande alarde é, expresso em termos diferentes, não muito controverso ou novo. em outras palavras, Wegner parece estar se estabelecendo como um iconoclasta intelectual ou acadêmico em seu estilo de propósito ... e quem é a comunidade do TCS para negar a ele esse enquadramento melodramático? no entanto, veja [2] uma refutação séria.

O exemplo de Wegner de dirigir um carro é muito relevante e outras importantes descobertas recentes no TCS podem ser citadas:

• o desafio da corrida de estrada DARPA e também a aproximação do Google com a tecnologia de um carro de condução. [3]
• o caso da vitória do Big Blue AI sobre Kasparov
• a recente vitória do Deep Blue Jeopardy Challenge
• o rover cada vez mais autônomo de Marte
• um avanço anunciado recentemente no reconhecimento de objetos não supervisionados pelo Google. [4]
• reconhecimento de fala comercializado

mas é verdade, o que começou décadas atrás como mera teoria com TMs agora é um fenômeno do mundo real e segmentos da comunidade TCS da torre de marfim podem estar em alguma resistência ou até negação desse fato e na associação fundamental e próxima [perto de Kuhnian]. ] transformação e mudança "atualmente em execução". isso é um tanto irônico, porque Turing foi muito aplicado em muitas de suas perspectivas e estudos, como seu interesse em um teste operacional de IA (o teste de Turing), dinâmica química, computação em resolução de xadrez, etc. [5].

você pode até ver isso em um microcosmo neste site em confrontos sobre como definir o escopo e discussões acaloradas sobre se uma etiqueta aparentemente aparentemente inócua chamada aplicação da teoria é legítima. [7]

e vamos notar que o TCS está de fato estudando muitos modelos interativos de computação e muita pesquisa importante está acontecendo nessa área ... particularmente sistemas de prova interativa dos quais todas as classes importantes de computação podem ser definidas em termos de. [6]

[1] A tese de Church-Turing - quebrando o mito de Goldin & Wegner

[2] Existem novos modelos de computação? uma resposta a Goldin & Wegner por Cockshott & Michaelson

[3] Googles carros autônomos - 300K milhas registradas, nenhum acidente sob controle de computador, o Atlântico

[4] Reconhecimento de objeto não supervisionado do Google de imagens do YouTube

[5] Contribuições de Alan Turings para o CS

[6] Paisagem de sistemas interativos de prova

[7] Modificando nosso escopo - uma proposta