Czy każdy program można wdrożyć mechanicznie?

Czy można zbudować mechaniczną implementację powiedzmy Microsoft Word w jednym celu (bez Turinga)? Czy można wdrożyć takie rzeczy jak iteratory, funkcje pierwszego rzędu, całą gamę technik programowania? Czy koła zębate i inne części mechaniczne mogą reprezentować struktury danych, a nawet obiekty programu? Czy w pewnym momencie wymaga to zbudowania maszyny ogólnego przeznaczenia równoważnej Turingowi, czy też każda funkcja, zmienna itp. Może mieć swoją własną unikalną konstrukcję mechaniczną w postaci kół zamachowych i / lub kół zębatych, zapadek, co masz? Podsumowując, zastanawiam się, czy jakieś oprogramowanie na standardowym komputerze mogłoby zostać skompilowane do mechanicznego planu.

— Alex Nye
źródło

Wydaje mi się, że coś, co uruchamia Microsoft Word, nawet nie musi działać na maszynie Turinga, ponieważ wszystkie procedury w programie Word powinny (możliwe) zostać zakończone (z wyjątkiem błędu ofc), oprócz głównej pętli zdarzeń.

— Realz Slaw

Tak jest !

— Pratik Deoghare

Jeśli jest to możliwe - co wydaje się prawdopodobne - powinno być możliwe stworzenie niekompletnej maszyny, która działa jak kompilator, tworząc plany dla innych maszyn z kodu źródłowego. Maszyny, które same mogą lub nie są kompletne.

— Nick Johnson

@Realz Slaw: nie, jeśli dołączasz makra I / O, VBA lub rozszerzenia. Na przykład wątpię, czy Word narzekałby, gdybyś dostarczył mu nieskończony dokument Worda. Prawdopodobnie jest to podstawowy system operacyjny, który osiągnąłby limit.

— reinierpost

@reinierpost, ale każda procedura nie musi być kompletna; albo byłyby możliwe do rozwiązania, albo możliwe, że nie. Tzn. Jeśli dostarczysz mu nieskończony dokument, prawdopodobnie nie wygasa. Chodzi mi o to, że większość tworzonych przez nas programów nie musi używać pełnego języka Turinga, ponieważ możemy ograniczyć go do programów, które możemy udowodnić, że są zakończone, biorąc pod uwagę dane nieskończone, i nie kończą się, jeśli otrzymają dane nieskończone; a jeśli możesz to zrobić, nie ma problemu z Zatrzymaniem. TLDR; jeśli nie możesz udowodnić, że twoje procedury zostały zakończone czy nie, jesteś okropnym programistą.

— Realz Slaw,

Odpowiedzi:

Tak to jest. Oto jak to zrobić:

Możesz skompilować w zasadzie dowolny program, który lubisz układać. Zobacz na przykład pracę Dana Ghicy i jego współpracowników nad Geometry of Synthesis, która pokazuje, jak kompilować programy w obwody.

Dan R. Ghica. Geometria syntezy: ustrukturyzowane podejście do projektowania VLSI
Dan R. Ghica, Alex Smith. Geometria syntezy II: od gier do obwodów niewrażliwych na opóźnienia
Dan R. Ghica, Alex Smith. Geometria syntezy III: Zarządzanie zasobami poprzez wnioskowanie na podstawie typu.
Dan R. Ghica, Alex Smith, Satnam Singh. Geometria syntezy IV: kompilacja rekurencji afinicznej w sprzęcie statycznym.

Następnie obwody ponownie pojawiają się w inżynierii. John Baez podaje obszerną tabelę analogii pojęć i opracowuje wiele powiązań w Finds tego tygodnia 288-296. Tak więc schematy połączeń generowane przez kompilatora Dana mogą być tworzone jako systemy mechaniczne lub hydrauliczne, jeśli naprawdę tego chcesz!

╔══════════════════════════════════════════════════════════════╗
║                 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              ║
╚══════════════════════════════════════════════════════════════╝

— Neel Krishnaswami
źródło

Następstwo: patenty na oprogramowanie nie mają sensu.

— András Salamon,

Fantastyczna odpowiedź na pytanie, które ledwo umiałem zadać. Dzięki za dodany wykres!

— Alex Nye

Praktycznym tego przykładem jest komputer Kółko i krzyżyk wykonany z Tinker Toys w Boston Science Museum (pierwotnie wykonany przez zespół studentów MIT). Oczywiście jest to o wiele prostsze niż Microsoft Word.

Oto artykuł z 1989 roku opublikowany przez Scientific American.

Były też maszyny Turinga wykonane z legosu (to trochę oszukuje, ponieważ do poruszania się wykorzystuje prąd - rzeczywiście komputer - ale myślę, że projekt mógłby zostać zmodyfikowany, aby tego uniknąć) złom i więcej.

— SamM
źródło

Podobał mi się artykuł i maszyna Lego, dzięki.

— Alex Nye

Próbując odnieść się konkretnie do przykładu tworzenia edytora sprzętowego, powstał wczesny eksperymentalny komputer, który zaimplementował zarówno system operacyjny, jak i edytor całkowicie sprzętowo. Później edytor został zastąpiony oprogramowaniem, co znacznie zmniejszyło potrzebny sprzęt. Zostało to opisane w książce o architekturze i historii komputerów. Niestety zapomniałem nazwy i nie znalazłem słów kluczowych, aby wyśledzić oryginalne źródło.

— Bill Simpson
źródło