Existe um nome para "coisas físicas das quais se pode construir uma máquina de Turing"?

16

Uma das coisas surpreendentes da ciência da computação é que a implementação física é, em certo sentido, "irrelevante". As pessoas construíram computadores com sucesso em vários substratos diferentes - relés, tubos de vácuo, transistores discretos etc. Em breve, as pessoas poderão construir computadores completos de Turing a partir de materiais ópticos não lineares, várias biomoléculas e alguns outros substratos. Em princípio, parece possível construir um computador com bola de bilhar .

No entanto, o substrato físico não é completamente irrelevante. As pessoas descobriram que certos conjuntos de componentes - em particular, a lógica do diodo-resistor - são "incompletos": não importa quantos deles você conecte a uma fonte de alimentação e entre si, há certas coisas muito simples que ela não pode Faz. (A lógica diodo-resistor pode implementar AND, OR, mas falha na implementação de NOT). Além disso, certas maneiras de conectar componentes - em particular os perceptrons de camada única - são "incompletos": existem certas coisas muito simples que eles não podem fazer. (Um perceptron de camada única pode implementar AND, OR, NOT, mas falha na implementação do XOR).

Existe uma frase menos incômoda para "coisas físicas das quais se pode construir uma máquina de Turing"? Ou, pelo contrário, "coisas físicas que, por mais que se tenha, não podem formar uma máquina de Turing"?

Por um tempo, usei a frase "conjunto funcionalmente completo" ou "conjunto universal de portas" - ou, quando falo com matemáticos, "coisas físicas que podem implementar um conjunto funcionalmente completo" - mas me disseram que não é ' t bastante correto. Alguns conjuntos de componentes podem implementar um conjunto funcionalmente completo; e, no entanto, não é possível construir uma máquina completa de Turing totalmente a partir desses componentes. Por exemplo, lâmpadas e interruptores de 4 vias operados manualmente podem implementar um conjunto funcionalmente completo (AND, OR, NOT, XOR etc.); e, no entanto, não é possível construir uma máquina completa de Turing inteiramente com interruptores e lâmpadas, uma vez que a saída (elétrica ou óptica) de uma não pode ser alimentada na entrada (rotativa mecanicamente) da próxima.

relacionado: Existe um nome oficial para uma noção de "reutilizável universal"? e Existe um nome para "chips dos quais se pode construir uma CPU"?

David Cary
fonte
11
Esta não é uma resposta, mas não posso postar comentários e senti a necessidade de fornecer o link para esta incrível história em quadrinhos do xkcd: [A Bunch of Rocks] [1], que está relacionada a esta pergunta :). [1]: xkcd.com/505
Zenon

Respostas:

3

Acredito que um termo apropriado seja "uma implementação física da Máquina de Turing".

PNP, então seria improvável que um cientista da computação os resolvesse.

Você pode ler mais no artigo de Scott Aaronson, NP-complete Problems and Reality Physical , especialmente na seção Computação analógica e de relatividade.

Você também pode encontrar uma implementação de lego (com fita finita) na seguinte página: http://legoofdoom.blogspot.com/

chazisop
fonte
+1 para os Legos - whee! Eu esperava encontrar uma frase um pouco mais fácil de entender do que "A implementação física de uma máquina de Turing pode ser composta desse conjunto de partes" - mas isso ainda é muito melhor do que as alternativas que eu já vi até agora.
David Cary
4

A física modela a realidade com teorias que definem um conceito de estado dependente do tempo associado a um sistema e um operador de evolução do tempo que descreve como esse estado evolui. Assim que você encontrar um sistema físico que (após alguma discretização do espaço de estados) implemente o espaço de estados da sua máquina de Turing, e que tenha termos de interação que implementem (talvez após alguma discretização do tempo) a evolução do tempo de acordo com a tabela de transição de estados de sua máquina de Turing em seu espaço de estado, você encontrou um modelo físico completo de Turing do seu sistema. Assim, você pode argumentar que seu sistema "é" completo em Turing.

Ao analisar a computação quântica, você encontrará discussões sobre implicações que as teorias físicas têm no modelo de computação de Turing. Por exemplo, as teorias físicas precisam ser reversíveis. Uma propriedade que não é compartilhada por máquinas Turing comuns. No entanto, não há perda de generalidade, pois qualquer máquina de Turing pode ser simulada por uma máquina reversível, com alguma sobrecarga que pode compensar tempo versus espaço, etc.

Martin Schwarz
fonte
Este texto está repleto de conceitos e terminologia interessantes. Infelizmente, não vejo nenhuma frase aqui que possa ser usada como "Este é um conjunto de componentes <phrase>, enquanto esses são um conjunto de <notphrase> componentes".
David Cary
3

Apenas pensei em salientar que a integridade de um meio físico para simular a lógica necessária para fabricar uma máquina de computação completa Turing pode ser estabelecida apenas na capacidade de incorporar um portão NAND, pois todos os outros portões podem ser derivados dos portões NAND (um pode perguntar o que compreende os portões da NAND, e essa é uma pergunta muito inteligente, mas são os portões da NAND até o fim!).

Você deve examinar o trabalho de Charles Babbage e as pessoas que ele inspirou. Babbage criou um computador físico para tabular funções polinomiais em tabelas impressas para índices de matemática (no passado, você tinha pilhas de livros que não tinham nada além de nomes de funções seguidos de folhas de valores de f (x)). Ele começou a trabalhar no que seria se tornaram um computador completo da Turing usando câmaras de engrenagens e tal. Acredito que seu filho continuou seu trabalho e a única manifestação física de seus esforços combinados foi uma ULA mecânica em pleno funcionamento, que é a base dessas calculadoras mecânicas que você pode ou não conhecer. No entanto, o financiamento para esses projetos caiu como um computador mecânico no tamanho e maneira que eles poderiam ser feitos naquele tempo, era muito impraticável. No entanto, desde então, e especialmente em eventos recentes, as pessoas passaram e estão promovendo a pesquisa de Charles Babbage. Essa abordagem pode ter sua última gargalhada, pois há quem pense que a única maneira de tornar as CPUs seriais mais rápidas do que agora é implementar algumas dessas abordagens mecânicas em uma CPU, evitando os problemas decorrentes dos eletromagnéticos em uma escala menor que o que usamos agora. Aparentemente, a mecânica funciona em qualquer escala.

Da mesma forma, o trabalho foi feito no que é chamado de computador quântico, que busca facilitar grandes cálculos por meio da teoria quântica. Não tenho muita certeza de como tudo funciona. Mas apela fisicamente a experimentos de física de partículas que se baseiam na teoria quântica.

Tenho certeza de que muitos outros meios diferentes de computação estão sendo explorados, até rochas no deserto, mas deles não tenho experiência.

acp10bda
fonte
Lâmpadas e interruptores de luz podem implementar NAND. Há uma configuração de 2 interruptores de luz comuns e uma lâmpada de saída (e uma segunda lâmpada oculta) em que a lâmpada de saída permanece BRILHANTE, exceto quando um ser humano liga os dois interruptores para LIGADO, a lâmpada de saída fica ESCURA. Infelizmente, aparentemente (?) Não é possível construir uma máquina completa de Turing inteiramente com interruptores de luz e lâmpadas. Existe algum termo que eu possa usar que inclua o NAND 74HC132, mas exclua o NAND dos interruptores e lâmpadas?
David Cary
Bem, o problema é que a entrada é mecânica e a saída é elétrica; portanto, os comutadores são como um portão de conversão e entre dois domínios (cinética em eletrônica). Supondo que ele funcione como um nandgate que você PODE criar um computador completo Turing com eles, é necessário facilitar a conversão entre esses dois meios para fazer com que a saída de um portão seja inserida no outro, possivelmente um comutador motorizado, mas sim impraticável. Um termo que você poderia usar e que agora vou maquiar agora é nandgate do mesmo meio, que estipula que a entrada e a saída estão no mesmo meio.
acp10bda
+1 de boa ideia - crie um termo e defina-o exatamente para o que estou procurando. O conjunto {(uma caixa com 2 interruptores de luz de entrada e uma lâmpada de saída que implementa AND), (um comutador motorizado ativado por luz que implementa NOT)} é um conjunto em cascata d-universal. Mas o conjunto {lâmpadas, interruptores de luz} sozinho não é um conjunto em cascata d-universal.
David Cary
É possível construir uma máquina de Turing a partir de coisas que não são nandgates do mesmo meio?
David Cary
Desculpe pelo atraso desta resposta, mas sim. Uma máquina de Turing pode ser feita a partir de qualquer conjunto de componentes usando qualquer variedade de mídias de entrada e saída, desde que os componentes estejam dispostos de tal maneira que o resultado seja um mecanismo completo de Turing. No entanto, considerando que o meio de computação se tornaria uma variação tão descontrolada e potencialmente muito interessante para assistir ao trabalho, eu gostaria de me referir a um mecanismo como um mecanismo completo de Rube-Goldberg-Turing. :)
acp10bda