Existe uma analogia física com a máquina de Turing?

Recentemente, na minha turma de CS, fui apresentado à máquina de Turing.

Após a aula, passei mais de duas horas tentando descobrir qual é a relação entre uma fita e uma máquina.

Eu desconhecia completamente a existência de fitas de computador ou como as fitas e máquinas interagiam até hoje. Ainda não consigo entender por que uma máquina lê fitas, mas um scanner talvez seja uma concepção mais próxima da máquina de Turing, onde o papel é considerado uma fita e o que entra no scanner é o que uma máquina de Turing faria.

Mas, de qualquer forma, a idéia de uma máquina de Turing não é bastante arcaica? Temos tantos dispositivos físicos (em vez de hipotéticos) em nosso escritório ou sala de estar que parecem fazer o que a Máquina de Turing faz.

Alguém pode dar um exemplo melhor tirando da realidade para que as funcionalidades essenciais dessa concepção hipotética sejam capturadas?

As máquinas de Turing são um dos modelos de computação completos "originais" de Turing, junto com o cálculo e as funções recursivas definidas recursivamente. Atualmente, em muitas áreas da ciência da computação teórica, um modelo diferente é usado, a máquina de RAM, muito mais próxima dos computadores reais. Como os dois modelos são equivalentes em p (eles se simulam com, no máximo, uma explosão polinomial), do ponto de vista de perguntas como P vs. NP, ambos os modelos são equivalentes.$\lambda$

AFAIK, a Máquina de Turing, é modelada com base na idéia de um ser humano com caneta e papel. O humano tem um certo estado no cérebro, olha para o papel como a máquina olha para a fita e escreve algo no papel ou se move para olhar para um lugar diferente, assim como a máquina.

A TM é arcaica como a aritmética de número natural Peano. A MT é inútil para computação prática e, é claro, não se destina a ser usada para isso. É apenas uma maneira simples de axiomatizar a computação, para que possamos raciocinar sobre o que é computável e o que não é - assim como a aritmética do Peano é útil para definir, desde os primeiros princípios, o que são números naturais e quais são suas propriedades - mas seria ridículo. tente fazer aritmética manipulando números de Peano manualmente, de acordo com as definições teóricas.

Apenas pense como seria difícil provar diferentes teoremas da teoria da complexidade e da computabilidade (por exemplo, provar que o Problema de Halting é indecidível), se você tivesse que prová-los usando a semântica da linguagem de programação C ++ em vez da Máquina de Turing. Suas provas seriam ridículas ou impossíveis - tão ridículas quanto provar a associatividade da multiplicação natural de números usando o método da escola aplicado a números inteiros decimais como sua definição do que é multiplicação.

Muitos modelos de computação completos de Turing muito diferentes são fisicamente realizáveis ​​(até considerar o infinito como sendo ilimitado). Portanto, esse não pode ser o ponto para escolher um modelo.

A resposta de @jkff é apropriada ao observar que a Máquina de Turing se destina a ser um dispositivo teórico com o objetivo matemático de estudar a computabilidade e a provabilidade (que surgem realmente no contexto do problema de Entscheidungs de Hilbert ). Mas não é muito preciso nas razões para escolher um formalismo simples.

Provar, em princípio, o problema da parada não é muito mais difícil com modelos mais avançados. De fato, nossas "provas" geralmente são apenas a construção de uma solução. Não entramos muito nos argumentos reais (muito tediosos) de que essas construções estão corretas. Mas quem escreve um intérprete para uma linguagem completa de Turing faz tanto quanto qualquer construção como uma máquina universal. Bem, C pode ser um pouco complicado, e podemos querer simplificá-lo um pouco para esse fim.

A importância de se ter um modelo simples reside muito mais no uso que pode ser feito do modelo do que no estabelecimento de suas propriedades (como o Problema de Halting, para dar o exemplo dado por @jkff).

Normalmente, grandes teoremas são geralmente teoremas que podem ser expressos de maneira muito simples e são aplicáveis ​​a uma ampla gama de problemas. Mas eles não são necessariamente teoremas fáceis de provar.

No caso da MT, a importância da simplicidade é que muitos resultados são estabelecidos pela redução do Problema da Parada, ou outros problemas da MT, a problemas nos quais estamos interessados ​​(como a ambigüidade de linguagens livres de contexto), estabelecendo limitações inerentes à solução. estes problemas.

De fato, embora seja muito intuitivo (o que provavelmente é o principal motivo de sua popularidade), o modelo da MT geralmente não é simples o suficiente para ser usado nessas provas. Essa é uma das razões da importância de outros modelos ainda mais simples, como o Problema Pós-Correspondência , menos intuitivo de analisar, mas mais fácil de usar. Mas isso ocorre porque esses modelos computacionais são frequentemente usados ​​para provar resultados negativos (que remontam ao problema original de Entscheidung).

No entanto, quando queremos provar resultados positivos, como a existência de um algoritmo para resolver algum problema, a MT é um dispositivo muito simplista. É muito mais fácil considerar modelos avançados de modo, como o computador RAM , ou um computador de memória associativa , ou um dos muitos outros modelos, ou mesmo simplesmente uma das muitas linguagens de programação.

Em seguida, o modelo de TM vem apenas como um ponto de referência, em particular para a análise de complexidade, dada a complexidade de reduzir esses modelos ao modelo de TM (geralmente polinomial). para dar um exemplo extremo, às reduções do cálculo Lambda).

Em outras palavras, o modelo da MT é muitas vezes simplista demais para projetar e estudar algoritmos (resultados positivos) e muitas vezes complexo demais para estudar a computabilidade (resultados negativos).

Mas parece estar no lugar certo para servir como um elo central para conectar tudo isso, com a grande vantagem de ser bastante intuitivo.

Em relação às analogias físicas, não há razão para escolher um modelo em detrimento de outro. Muitos modelos completos de computação de Turing são fisicamente realizáveis (até o limite para o infinito da memória), uma vez que não há razão para considerar um computador junto com seu software menos físico do que um computador "nu". Afinal, o software possui uma representação física, que faz parte do computador programado. Portanto, como todos os modelos de computação são equivalentes desse ponto de vista, é melhor escolhermos um que seja conveniente para a organização do conhecimento.

Imagine um recém-chegado à geometria perguntando:

Existe uma analogia física para o triângulo?

A idéia de um triângulo não é bastante arcaica? Temos tantas formas físicas (e não hipotéticas) em nosso escritório ou sala de estar que parecem fazer o que o triângulo faz.

O que você responderia?

Você pode dizer que essas perguntas revelam dois equívocos fundamentais sobre triângulos:

1. "Triângulos são puramente hipotéticos". Errado! Enquanto são entidades matemáticas, ideais platônicos e hipotéticos nesse sentido, triângulos são reais : podemos realmente construí-los no mundo real. É verdade que o que construímos nunca será um triângulo perfeito, mas nossa teoria matemática sobre eles se aplica ao mundo real, as leis que podemos derivar se aplicam a formas no mundo real, a teoria pode ser usada como base para o design, construir e medir formas no mundo real; essa é a razão pela qual a teoria foi desenvolvida em primeiro lugar.
2. "Triângulos são inúteis porque não descrevem as formas que normalmente usamos".Errado! Descrever formas reais que você encontra no mundo real não é o objetivo delas. Se todo o seu escritório ou sala de estar não contém um único triângulo, isso não significa que o conceito de triângulo seja irreal ou desatualizado e é melhor substituí-lo por outra coisa. Seu principal objetivo é como uma construção elementar a partir da qual todas as formas mais complexas podem ser construídas em princípio - e para a qual podemos, portanto, derivar leis que se aplicam às formas em geral. Raciocinar sobre triângulos nos permite raciocinar sobre formas em geral. Sua sala de estar está sujeita às mesmas leis que derivamos para triângulos, e nosso conhecimento dessas leis foi usado, direta ou indiretamente, para construí-la. A sala de estar provavelmente não possui um único triângulo, muito menos um perfeito, mas não nos preocupamos em encontrar triângulos ali; podemos. no entanto, crie uma descrição das formas, aproximando-as com triângulos, e isso - triangulação - é uma coisa popular e útil a se fazer. Portanto, triângulos são blocos de construção para nos ajudar a pensar em formas em geral.

O mesmo vale para as máquinas de Turing.

Faz tanto tempo desde que fui apresentado à geometria, realmente não me lembro se algum recém-chegado realmente tem esses conceitos errados sobre triângulos. Mas quando se trata de máquinas de Turing, encontro esses conceitos errados o tempo todo . Com tanta frequência, de fato, parece haver algo fundamentalmente errado com a maneira como eles geralmente são ensinados. Talvez uma abordagem show and tell esteja em ordem!

Então, por uma questão de integridade:

1. "As máquinas de Turing são puramente hipotéticas". Errado! Embora sejam entidades matemáticas, ideais platônicos e hipotéticos nesse sentido, as Máquinas de Turing são reais : podemos realmente construí-las no mundo real. É verdade que o que construímos nunca será uma Máquina de Turing perfeita, mas nossa teoria matemática sobre eles se aplica ao mundo real, as leis que podemos derivar se aplicam a dispositivos de computação no mundo real, a teoria pode ser usada como base para projetar, construir e medir dispositivos de computação no mundo real; essa é a razão pela qual a teoria foi desenvolvida em primeiro lugar.
2. "As máquinas de Turing são inúteis porque não descrevem os dispositivos de computação que normalmente usamos".Errado! Descrever os dispositivos de computação reais que você encontra no mundo real não é o objetivo deles. Se todo o seu back office ou estúdio de entretenimento doméstico não contém uma única máquina de Turing, isso não significa que o conceito de máquina de Turing seja irreal ou desatualizado e é melhor substituí-lo por outra coisa. Seu principal objetivo é como uma construção elementar a partir da qual todos os dispositivos de computação mais complexos podem ser construídos em princípio - e para o qual podemos, portanto, derivar leis que se aplicam às formas em geral. O raciocínio sobre as máquinas de Turing nos permite argumentar sobre dispositivos de computação em geral. O hardware e o software do seu computador estão sujeitos às mesmas leis que derivamos para a Turing Machines, e nosso conhecimento dessas leis foi usado, direta ou indiretamente, para construí-las - mesmo que provavelmente não Não há uma única máquina de Turing. É nas leis que estamos interessados.

A analogia física que Turing parece ter em mente é um computador solucionando problemas com lápis, papel e borracha. Você deve entender que em 1936, um "computador" era uma pessoa empregada para calcular. É claro que em 1936 a maioria dos computadores usaria máquinas de somar, mas Turing não as menciona por serem desnecessárias. Aqui está o que ele diz, com relação à fita, ao tentar justificar que "os números 'computáveis' [isto é, aqueles que uma máquina de Turing poderia computar] incluem todos os números que naturalmente seriam considerados computáveis"

A computação é normalmente feita escrevendo certos símbolos no papel. Podemos supor que este artigo seja dividido em quadrados como o livro aritmético de uma criança. Na aritmética elementar, o caráter bidimensional do papel é usado algumas vezes. Mas esse uso é sempre evitável, e acho que será acordado que o caráter bidimensional do papel não é essencial para a computação. Suponho então que o cálculo seja realizado em papel unidimensional, ou seja, em uma fita dividida em quadrados.

Embora o computador não seja mais um negócio, a última vez que verifiquei, as crianças ainda estavam sendo ensinadas a executar algoritmos usando lápis e papel como meio de armazenamento. Portanto, embora essa analogia possa parecer antiquada ou até arcaica, ainda não é obsoleta.

Para obter mais informações, consulte Sobre números computáveis ​​com um aplicativo para o problema de entscheidung , especialmente as seções 1 e 9.

@jkff tem a idéia sobre the Turing Machine is modeled on the idea of a human with a pen and papernão é totalmente correto. Mas há muitas situações em que isso pode ser considerado correto.

Pense no humano como uma máquina de Turing sob certa projeção dos estados. Em outras palavras, se você vê um ser humano apenas durante o horário de trabalho, ele realiza determinadas tarefas. Essas tarefas são as tarefas básicas do trabalho.

Se você não se importa com a vida pessoal dele, o que ele faz em casa, no quarto dele, etc. Você pode considerar isso como projetar sua função de transição em uma nova função de transição na qual os estados não relacionados ao trabalho são ignorados. Em outras palavras, você pode pular todos os estados e tarefas que nada têm a ver com sua preocupação e perspectiva.

Nesse modelo, a máquina de Turing é modelada após um humano com uma caneta, papel realizando uma tarefa fixa (ou seja, visualizar em uma perspectiva fixa). A fita é o que ele escreve no papel (ignorando todos os papéis ou escrevendo em algum papel que ele não escreve para a tarefa)

Agora, se você levar em conta outras tarefas que ele faz, o que você tem é que você tem uma união de muitas máquinas de Turing em um ser humano. Mas e se ele mudar de emprego e realizar tarefas diferentes. Então, seu estado cerebral muda para uma máquina de Turing diferente quando vista sob diferentes perspectivas em diferentes períodos de tempo.

Se você quer uma boa resposta para sua pergunta, acho que Yuval Filmus respondeu bem. Use o modelo de RAM. Fique com ele.