Czy istnieje nazwa „rzeczy fizycznych, z których można zbudować maszynę Turinga”?

Jedną z niesamowitych rzeczy w informatyce jest to, że fizyczne wdrożenie jest w pewnym sensie „nieistotne”. Ludzie z powodzeniem zbudowali komputery z kilku różnych podłoży - przekaźników, lamp próżniowych, dyskretnych tranzystorów itp. Ludzie mogą wkrótce odnieść sukces w budowie komputerów Turinga z nieliniowych materiałów optycznych, różnych biomolekuł i kilku innych podłoży. Zasadniczo wydaje się możliwe zbudowanie komputera do gry w bilard .

Jednak fizyczny substrat nie jest całkowicie nieistotny. Ludzie odkryli, że niektóre zestawy elementów - w szczególności logika rezystora diodowego - są „niekompletne”: bez względu na to, ile z nich podłączasz do źródła zasilania i między sobą, istnieją pewne bardzo proste rzeczy, których nie może robić. (Logika rezystora diodowego może implementować AND, OR, ale nie implementuje NOT). Ponadto niektóre sposoby łączenia komponentów - w szczególności jednowarstwowe perceptrony - są „niekompletne”: są pewne bardzo proste rzeczy, których nie mogą zrobić. (Perceptron jednowarstwowy może implementować AND, OR, NOT, ale nie implementuje XOR).

Czy istnieje mniej niezręczne określenie „rzeczy fizyczne, z których można zbudować maszynę Turinga”? Lub przeciwnie: „rzeczy fizyczne, które bez względu na to, ile ich ma, nie mogą tworzyć maszyny Turinga”?

Przez jakiś czas używałem wyrażenia „funkcjonalnie kompletny zestaw” lub „uniwersalny zestaw bram” - lub, rozmawiając z matematykami, „rzeczy fizyczne, które mogą zaimplementować funkcjonalnie kompletny zestaw” - ale powiedziano mi, że to nie „ całkiem poprawne. Niektóre zestawy komponentów mogą implementować funkcjonalnie kompletny zestaw; a jednak nie jest możliwe zbudowanie kompletnej maszyny Turinga w całości z tych komponentów. Na przykład żarówki i ręcznie sterowane 4-kierunkowe przełączniki światła mogą implementować funkcjonalnie kompletny zestaw (AND, OR, NOT, XOR itp.); a jednak nie jest możliwe zbudowanie kompletnej maszyny Turinga całkowicie z wyłączników światła i żarówek, ponieważ wyjścia (elektrycznego lub optycznego) jednego nie można zasilić (mechanicznie obracającego się) wejścia następnego.

powiązane: Czy istnieje oficjalna nazwa pojęcia „uniwersalnego użytku”? i czy istnieje nazwa „chipów, z których można zbudować procesor”?

Uważam, że właściwym terminem jest „fizyczna implementacja maszyny Turinga”.

Głównym problemem każdej implementacji jest zapewnienie „nieskończonej taśmy” lub bardziej abstrakcyjnego poziomu, nieskończonej pamięci. Łatwym rozwiązaniem tego problemu jest użycie specjalnego symbolu wskazującego ostatni kwadrat taśmy. Kiedy maszyna Turinga do niej dotrze, przechodzi w specjalny stan, który wymaga interwencji użytkownika, który dostarcza dodatkową taśmę. Następnie TM może kontynuować działanie. Niestety, takie implementacje, które są „fizyczne”, wiążą się z fizyką. Jeśli wszechświat jest skończony i ze względu na skalę Plancka, dostępna jest skończona ilość taśmy. To tutaj powstają problemy, na które być może nie mogą odpowiedzieć informatycy, ale fizycy. Zauważ, że fizycy nie doszli do wniosku w tych kwestiach, które są uważane za główne otwarte problemy wielkości$P \neq NP$, więc jest mało prawdopodobne, aby informatyk je rozwiązał.

Możesz przeczytać więcej w artykule Scotta Aaronsona „ NP-complete Problems and Physical Reality” , szczególnie w części poświęconej obliczeniom analogowym i teorii względności.

Możesz również znaleźć implementację Lego (z skończoną taśmą) na następującej stronie: http://legoofdoom.blogspot.com/

Fizyka modeluje rzeczywistość za pomocą teorii, które definiują pojęcie stanu zależnego od czasu powiązanego z systemem oraz operatora ewolucji czasu opisującego ewolucję tego stanu. Gdy tylko znajdziesz fizyczny system, który (po pewnej dyskretyzacji przestrzeni stanów) implementuje przestrzeń stanu maszyny Turinga i zawiera warunki interakcji, które implementują (być może po pewnym czasie dyskretyzacji) ewolucję czasu zgodnie z tabelą przejścia stanu na swojej maszynie Turinga w jej przestrzeni stanów, znalazłeś kompletny model fizyczny systemu Turinga. Zatem można argumentować, że twój system „jest” kompletny w Turinga.

Patrząc na obliczenia kwantowe, można znaleźć omówienie wpływu teorii fizycznych na model obliczeń Turinga. Na przykład teorie fizyczne muszą być odwracalne. Właściwość, która nie jest współdzielona przez zwykłe maszyny Turinga. Jednak nie ma żadnej straty w ogólności, ponieważ każda maszyna Turinga może być symulowana przez maszynę odwracalną, z pewnym narzutem, który może zastąpić czas w stosunku do przestrzeni itp.

Pomyślałem, że zwrócę uwagę na to, że kompletność fizycznego medium do symulacji logiki wymaganej do stworzenia kompletnej maszyny komputerowej Turinga można ustalić wyłącznie w jej zdolności do wcielenia bramki NAND, ponieważ wszystkie inne bramki można uzyskać z bramek NAND (jedna może zapytać, co składa się na bramy NAND, i to bardzo sprytne pytanie, ale to bramy NAND aż do samego końca!).

Powinieneś spojrzeć na twórczość Charlesa Babbage'a i ludzi, których inspirował. Babbage stworzył komputer fizyczny do zestawiania funkcji wielomianowych w tabele drukowane dla indeksów matematycznych (w czasach, w których mielibyście stosy książek, które nie miały nic poza nazwami funkcji, a następnie arkuszami wartości f (x)). Następnie zaczął pracować nad tym, co by stały się kompletnym komputerem Turinga używającym kół zębatych i tym podobnych. Jego syn, wierzę, że kontynuowano jego pracę, a jedynym fizycznym przejawem ich połączonych wysiłków była w pełni funkcjonalna mechaniczna ALU, która jest podstawą tych mechanicznych kalkulatorów, o których możesz wiedzieć lub nie. Jednak finansowanie tych projektów spadło jako komputer mechaniczny, ponieważ wielkość i sposób ich realizacji w tym czasie były bardzo niepraktyczne. Jednak od tego czasu, a zwłaszcza w ostatnich wydarzeniach, ludzie przeszli i kontynuują badania Charlesa Babbage'a. To podejście może mieć ostatni śmiech, ponieważ są tacy, którzy myślą, że jedynym sposobem na szybsze wykonanie szeregowych procesorów niż teraz byłoby wdrożenie niektórych z tych mechanicznych podejść w procesorze, zapobiegając problemom powodowanym przez elektromagnetyczne na skalę mniejszą niż ten, którego używamy teraz. Pozornie mechanika działa w dowolnej skali.

Podobnie, prace nad tym, co nazywa się komputerem kwantowym, który ma na celu ułatwienie dużych obliczeń poprzez teorię kwantową, nie jestem do końca pewien, jak to wszystko działa. Ale fizycznie odwołuje się do eksperymentów fizyki cząstek, które opierają się na teorii kwantów.

Jestem pewien, że badanych jest wiele innych mediów obliczeniowych, nawet skały na pustyni, ale nie mam z nimi doświadczenia.