Jeśli abstrakcyjna maszyna może się symulować, czy to czyni Turinga kompletnym?

Na przykład w językach programowania często pisze się kompilator / interpreter X-w-X, ale na bardziej ogólnym poziomie wiele znanych systemów Turing-complete może symulować się w imponujący sposób (np. Symulując grę życia Conwaya w grze życia Conwaya ).

Moje pytanie brzmi zatem: czy system jest w stanie samodzielnie przeprowadzić symulację, aby udowodnić, że Turing jest gotowy? Z pewnością jest to warunek konieczny.

computability automata-theory turing-machines

— Jeremy Kun
źródło

Zanim spróbuję odpowiedzieć, czy możesz być bardziej szczegółowy, co rozumiesz przez „system logiczny może się symulować”? Czy masz na myśli coś w stylu „może zakodować własną składnię i sprawdzalność”?

— Andrej Bauer,

Co dokładnie rozumiesz przez „symulację”? W szczególności, w jaki sposób definiujesz symulację, aby nadal miała ona sens, np. W kontekście Gry Życia, ale nie czyni pytania całkowicie trywialnym (np. Maszyna, która nic nie symuluje maszyny, która nic nie robi)?

— Jukka Suomela,

Crosspost: math.stackexchange.com/q/78734/3330

— Raphael

Fasola, jednoczesne wysyłanie postów jest zdecydowanie odradzane na cstheory, proszę zobaczyć poilicy . ps: Nie jestem pewien, czy to pytanie dotyczy cstheory, sprawdź także FAQ, aby zrozumieć zakres cstheory.

— Kaveh

Maszyna „nic nie rób” może się symulować.

— Maks.

Odpowiedzi:

Niekoniecznie. Na przykład dwuwymiarowy blokowy automat komórkowy z dwoma stanami, w którym komórka staje się żywa tylko wtedy, gdy jej czterej poprzednicy mają dokładnie dwa sąsiednie żywe komórki, może symulować się ze współczynnikiem dwóch spowolnień i współczynnikiem powiększenia o dwóch rozmiarach, ale nie jest znane jako ukończenie Turinga. Więcej informacji na temat tego automatu blokowego oraz zasady B36 / S125 dla sąsiedztwa Moore, który jest w stanie symulować ten automat blokowy, można także znaleźć w Nathaniel Johnston B36 / S125 „2x2” Life-Like Cellular Automaton .

— David Eppstein
źródło

Co jeśli maszyna ma pewien stopień złożoności? Myślę, że musiałoby to być niezwiązane z kompletnością Turinga ...

— Jeremy Kun

Ale z drugiej strony automat blokowy, o którym wspomniałeś, wciąż może być ukończony. Mówisz tylko, że implikacja nie jest znana. Nie znaczy to, że reprezentuje kontrprzykład.

— Jeremy Kun,

Jeśli weźmie się pod uwagę tylko stany automatu blokowego ze skończoną liczbą żywych komórek, to przy tym ograniczeniu nadal można symulować się w ten sam sposób. Ale automat z ograniczeniami z pewnością nie jest ukończony przez Turinga, ponieważ żaden wzór nie może uciec przed otaczającym go diamentem, więc los każdego wzoru można ustalić tylko w czasie wykładniczym.

— David Eppstein,

Nie, nie jest. Znam dwie główne klasy technik unikania niespójności / kompletności Turinga.

Pierwszą linią ataku jest skonfigurowanie systemu tak, aby składnia mogła być arytmetyczna, ale twierdzenie Godela o stałym punkcie nie przechodzi. Dan Willard intensywnie nad tym pracował i zapewnił spójne, samoregulujące systemy logiczne. Sztuką jest wyeliminowanie symboli funkcji mnożenia i dodawania oraz zastąpienie ich podzielnością i odejmowaniem. Daje to wystarczającą moc do arytmetycznego przedstawienia składni, ale twierdzenie o stałym punkcie nie przechodzi, ponieważ mnożenie nie jest możliwe do udowodnienia.

Zobacz Dan Willard. Samo-weryfikujące się systemy aksjomatów, twierdzenie o niekompletności i pokrewne zasady refleksji . Journal of Symbolic Logic 66 (2001) str. 536-596.
Druga linia ataku pozwala na większe wykorzystanie ustalonych punktów, ale aby ustawić rzeczy tak, aby składnia nie była arytmetyczna. Najładniejsze systemy do tego celu to (IMO) oparte na wariantach logiki liniowej. Na przykład, w teorii afinicznych zestawów lekkich Kazushige Terui nawet pełna, nieograniczona zasada rozumienia zbioru jest zdrowa, ale ponieważ logika otoczenia teorii zbiorów jest liniowa (a zatem skurcz nie jest dozwolony), paradoks Russella nie jest możliwy do wyprowadzenia.

Intuicyjnym powodem niepowodzenia arytmetyki jest to, że lekka liniowa przestrzeń funkcji jest tak ustawiona, że wszyscy jej mieszkańcy są wielomianami. W rezultacie lekka liniowa wersja aksjomatów Peano nie może udowodnić całkowitego potęgowania (ponieważ potęgowanie liczb jednostkowych zajmuje czas wykładniczy), a zatem nie ma już izomorfizmu między liczbami naturalnymi a łańcuchami bitów. $A \multimap B$

Kazushige Terui. Teoria zbiorów afinicznych światła: naiwna teoria zbiorów czasu wielomianowego. Studia Logica, vol. 77, nr 1, s. 9–40, 2004.

Myślę, że ten artykuł jest bardziej dostępny po przeczytaniu następującego artykułu Yvesa Lafonta:

Y. Lafont, Miękka logika liniowa i czas wielomianowy , Informatyka teoretyczna 318 (wydanie specjalne na temat niejawnej złożoności obliczeniowej) str. 163-180, Elsevier (2004)

Teoria mnogości Terui jest bardzo ekspresyjna, ale trudno ją porównać z tradycyjnymi teoriami mnogości, ponieważ teorie teoretyczne nie są dobrym narzędziem do porównywania bardzo słabych układów. Na przykład teoria mnogości Terui'ego oczywiście nie może udowodnić całkowitego potęgowania, a zatem jej siła teoretyczna nie może sięgać nawet . Klasy złożoności są prawdopodobnie lepsze - są kompletne dla czasu politytime (może udowodnić, że każda funkcja polytime jest całkowita, ale nie więcej). $\omega$

Często myślę o tego rodzaju systemach jako dowodach koncepcji, że teoria złożoności może służyć jako podstawa dla niektórych rodzajów ultrafinityzmu.

— Neel Krishnaswami
źródło

Uważam twoją odpowiedź za fascynującą, @Neel. Czy mógłbyś mi zasugerować dobry punkt wyjścia do przeczytania o (1) lub (2)? Nieco bardziej interesuje mnie nauka o (1), jeśli to ma znaczenie.

— Aaron Sterling

Bardziej mnie interesuje (2): jak potężna jest teoria mnogości? Czy ma to związek z „nowymi fundamentami” Quinian?

— cody

@Neel - Ciekawa odpowiedź. Chciałbym również to samo, co Aaron - czy możesz zasugerować dobry punkt wyjścia dla (1). Dzięki

— Akash Kumar,

Rozważ następujący model maszyny. Maszyna z kodem , na wejściu , zawsze wyprowadza . $i$ $x$ $0$

Należy zauważyć, że każdy komputer w tym modelu jest powszechne, a dla wszystkich . $M$ $M(\langle \ulcorner M' \urcorner, x \rangle ) = M'(x) = 0$ $M', x$

To oczywiście nie jest kompletne Turinga, ale oczywiście ma uniwersalne maszyny.

— David Harris
źródło

0

$0$

I dał podobną odpowiedź na krzyżu post na Math.SE która nie otrzymała żadnych głosów w górę. :)

— Kaveh

@Kaveh: Jak na ironię, wydaje mi się, że źle oceniłem tę odpowiedź jako wcześniejszą od ciebie, dlatego też głosowałem, edytowałem i komentowałem tylko tutaj. Krzyżowanie może być takim bólem.

— res

@res, myślę, że poziom witryn tworzy różne wzorce głosowania. Na math.se nawet bardzo dobra odpowiedź innego użytkownika o wysokiej reputacji tutaj nie jest tak wysoko oceniana, więc uważam to za normalne. :) (Również moja odpowiedź nie jest tak jasna i zrozumiała, jak odpowiedź Davida tutaj.)

— Kaveh