Qualquer programa pode ser implementado mecanicamente?

13

É possível criar uma implementação mecânica de propósito único (não concluída em Turing), por exemplo, Microsoft Word? É possível implementar coisas como iteradores, funções de primeira ordem, toda a gama de técnicas de programação? As engrenagens e outras partes mecânicas representam estruturas de dados ou até objetos de programa? Em um determinado momento, isso requer a construção de uma máquina equivalente a Turing de uso geral, ou cada função, variável, etc., pode ter sua própria construção mecânica sob a forma de volantes e / ou engrenagens, catracas, o que você tem? Em resumo, pergunto-me se algum software em um computador padrão poderia ser compilado em um projeto mecânico.

computability pl.programming-languages machine-models ar.hardware-architecture Alex Nye
fonte
Eu acho que algo que executa o Microsoft Word nem precisa ser executado em uma máquina de Turing, pois todos os procedimentos no Word devem terminar (provavelmente) (exceto se houver um erro de ofc), além do loop do evento principal.
Realz Slaw
1
Sim senhor !
Pratik Deoghare 5/11
1
Se isso for possível - o que parece provável -, será possível criar uma máquina completa sem turing que atue como um compilador, criando blueprints para outras máquinas a partir do código-fonte. Máquinas que podem ou não estar completas.
perfil completo de Nick Johnson
@Realz Slaw: não se você incluir E / S, macros VBA ou extensões. Por exemplo, duvido que o Word reclamaria se você fornecesse um documento infinito do Word. Provavelmente é o sistema operacional subjacente que alcançaria um limite.
Reinierpost
@reinierpost mas cada rotina não precisa ser concluída; eles provavelmente terminariam ou provavelmente não. Ou seja, se você fornecesse um documento infinito, provavelmente não seria finalizado. Meu ponto era que a maioria dos programas que fazemos não tem que usar uma linguagem Turing completa, porque podemos limitá-lo a programas que nós pode provar termina, dado dados não-infinitos, e não terminará se dado dados infinitos; e se você puder fazer isso, não há problema com o problema da parada. TLDR; se você não pode provar que suas rotinas terminam ou não, você é um péssimo programador.
Realz Slaw

Respostas:

23

Sim, ele é. Aqui está como você faz isso:

Você pode compilar basicamente qualquer programa que você gosta de circuitos. Veja, por exemplo, o trabalho de Dan Ghica e seus colaboradores na Geometria da Síntese, que mostra como compilar programas em circuitos.

  1. Dan R. Ghica. Geometria de síntese: uma abordagem estruturada para o projeto VLSI
  2. Dan R. Ghica, Alex Smith. Geometria da síntese II: dos jogos aos circuitos insensíveis aos atrasos
  3. Dan R. Ghica, Alex Smith. Geometria da síntese III: Gerenciamento de recursos através de inferência de tipo.
  4. Dan R. Ghica, Alex Smith, Satnam Singh. Geometria da síntese IV: compilação de recursão afim em hardware estático.

Os circuitos acabam reaparecendo repetidamente na engenharia. John Baez apresenta uma grande tabela de analogias de conceitos e elabora muitas conexões, nos achados 288-296 desta semana. Portanto, os diagramas de circuitos que o compilador de Dan gera podem ser instanciados como sistemas mecânicos ou hidráulicos, se você realmente quiser!

╔══════════════════════════════════════════════════════════════╗
║                 displacement  flow      momentum     effort  ║
╠══════════════════════════════════════════════════════════════╣
║ Mechanics      position      velocity  momentum     force    ║
║ (translation)                                                ║
║                                                              ║
║ Mechanics      angle         angular   angular      torque   ║
║ (rotation)                   velocity  momentum              ║
║                                                              ║
║ Electronics    charge        current   flux         voltage  ║
║                                        linkage               ║
║                                                              ║
║ Hydraulics     volume        flow      pressure     pressure ║
║                                        momentum              ║
╚══════════════════════════════════════════════════════════════╝
  1. http://math.ucr.edu/home/baez/week288.html
  2. http://math.ucr.edu/home/baez/week289.html
  3. http://math.ucr.edu/home/baez/week290.html
  4. http://math.ucr.edu/home/baez/week291.html
  5. http://math.ucr.edu/home/baez/week294.html
  6. http://math.ucr.edu/home/baez/week296.html
Neel Krishnaswami
fonte
12
Corolário: as patentes de software não fazem sentido.
András Salamon
1
Resposta fantástica para uma pergunta que eu mal sabia fazer. Obrigado pelo gráfico adicionado!
Alex Nye
5

Um exemplo prático disso é o computador Tic Tac Toe, fabricado com a Tinker Toys no Boston Science Museum (originalmente feito por uma equipe de estudantes do MIT). Obviamente, isso é muito mais simples que o Microsoft Word.

Aqui está um artigo de 1989 da Scientific American que o descreve.

Também existem máquinas de Turing feitas de legos (isso engana um pouco porque usa eletricidade - de fato um computador - para movimento, mas acho que o design pode ser modificado para evitar isso) sucata e muito mais.

SamM
fonte
Gostei do artigo e da máquina lego, obrigado.
Alex Nye
1

Tentando abordar especificamente o seu exemplo de criação de um editor em hardware, havia um computador experimental inicial que implementava o sistema operacional e o editor inteiramente em hardware. Mais tarde, o editor foi substituído por software, o que reduziu substancialmente o hardware necessário. Isso foi descrito em um livro sobre arquitetura e história de computadores. Infelizmente, esqueci o nome e não encontrei as palavras-chave para rastrear a fonte original.

Bill Simpson
fonte