Eu construí um computador mecânico alimentado por bolas de gude. Quais são as suas limitações teóricas?

8

Nos últimos dois anos, construí um computador mecânico alimentado por bolas de gude e fiz dele um jogo. É semelhante ao antigo Digi-Comp II, exceto por duas diferenças principais:

  1. As peças são reposicionáveis ​​no quadro.
  2. Você pode conectar vários 'bits' juntos usando engrenagens. Quando um desses bits é invertido, ele inverte os outros bits conectados a ele.

O link acima descreve como funciona. Minha pergunta é: quais são suas limitações teóricas? Minha formação teórica em computação é fraca, então, por favor, ELI5.

edit: Não estou interessado nas limitações óbvias: velocidade (não vou ganhar nenhuma corrida lá ...), tamanho do tabuleiro ou número de bolas de gude. Estou mais interessado em suas limitações teóricas. Talvez ajude a dividi-lo em duas perguntas:

  1. Como pode ser provado (ou refutado) ser completo de Turing?
  2. Se mais de 3 bits de engrenagem estiverem conectados, o atrito se tornará muito grande para um mármore transformar todos eles de uma só vez. Isso cria limitações adicionais?

Obrigado - estou muito animado para ler suas respostas! Eu estive pensando sobre isso por um longo tempo.

complexity-theory turing-machines computer-architecture computation-models Paul Boswell
fonte
3
Deseja considerar um modelo idealizado (tamanho infinito da grade, infinitamente muitos mármores) ou a máquina específica disponível? Observando a melodia das tags que você escolheu, você pode refinar quais perguntas deseja resolver? O que pode ser calculado? Quão rápido as coisas podem ser computadas? Que perguntas sobre arquitetura você tem em mente?
Raphael
1
A maneira mais fácil de restringir os recursos do seu modelo é responder a essas perguntas. 1) O que são entrada e saída? 2) Quais portas lógicas você pode modelar? Estou perguntando 2) porque é claro que você não tem um computador universal lá; toda configuração de placa é um programa fixo e corresponde intimamente aos circuitos. Portanto, se você pode simular qualquer conjunto completo de portas (por exemplo, portas NAND), você tem um modelo completo de Turing (assumindo infinitas coisas). Como você não possui nenhum componente estático com duas entradas e uma única saída, não vejo imediatamente o que está acontecendo.
Raphael
2
Dito isto, projeto interessante! Informe-nos no bate - papo sobre ciência da computação quando for lançado.
Raphael
3
No vídeo, você diz: se você cria uma placa grande o suficiente, ela pode fazer o que qualquer computador pode fazer. Bem, sim e não: dado um computador, você pode (teoricamente) construir uma placa grande o suficiente, mas, dada uma placa, você pode construir um computador que precise de uma placa maior - e isso significa que suas placas não estão completas com Turing. A integridade de Turing exige operar em memória arbitrariamente grande , algo que suas placas não podem fazer. Toda máquina de Turing é o limite de uma série infinita de máquinas de Turing de fita finita, mas isso não torna as máquinas de Turing de fita finita Turing completas.
Reinierpost
2
Se você tornar a ampliação de uma placa parte da operação da máquina, ela se tornará Turing completa.
Reinierpost

Respostas:

3

O que você tem agora é um computador concreto. Não podemos compará-lo a um modelo computacional até que seja formalizado adequadamente.

Minha intuição é que o quadro possa ser modelado como uma arquitetura de fluxo de dados . Os modelos computacionais concebidos de acordo com esse paradigma podem ser completos para Turing, mas (como foi dito nos comentários) nenhum computador concreto será equivalente a Turing, e não acho que você deva se preocupar com isso. Todos os computadores reais são apenas metáforas de trabalho (imperfeitas) de modelos computacionais formais.

Se você vier à idéia de imitar mais de perto uma máquina de fluxo de dados equivalente a Turing, há alguns problemas que podem ser abordados para "fortalecer a metáfora", por assim dizer. A introdução de ciclos e a composição de máquinas seriam as duas coisas mais importantes, na minha opinião, mas acho que sua máquina já é incrível. Ele serve muito bem a seu propósito, e essas "melhorias" podem sacrificar sua usabilidade.

André Souza Lemos
fonte
Obrigado! E muito útil! Eu não sabia sobre a distinção entre arquitetura de fluxo de dados e, digamos, arquitetura de Von Neumann antes. Eu apenas imaginei que, se a placa fosse maior, uma arquitetura de Von Neumann poderia ser construída. Alguma chance de você oferecer uma definição ou um link para o que você quer dizer com "ciclos" e "composição"?
Paul Boswell
Para os ciclos, imagine que haja uma maneira de enviar os mármores de volta, para o início ou para alguma memória intermediária no meio. Isso permitiria calcular alguns tipos de funções recursivas primitivas. A composição das máquinas é semelhante à composição das funções; imagine que você poderia conectar a saída de uma placa à entrada de outras.
André Souza Lemos
Um computador von Neumann é um grande ciclo.
André Souza Lemos