Kategoria „maszyn Turinga”?

Zastrzeżenie: Wiem bardzo mało o teorii złożoności.

Przepraszam, ale tak naprawdę nie ma sposobu, aby zadać to pytanie bez (strasznie) zwięzłego:

Jakie powinny być morfizmy w „kategorii” maszyn Turinga?

Jest to oczywiście subiektywne i zależy od interpretacji teorii, więc odpowiedź na to pytanie powinna idealnie dać pewne dowody i uzasadnienie również na poparcie tej odpowiedzi.

Chciałbym podkreślić, że szukam kategorii maszyn Turinga, a nie na przykład języków formalnych . W szczególności uważam, że moje morfizmy powinny zawierać dokładniejsze informacje niż redukcje itp. (Choć nie jestem pewien).

Oczywiście, jeśli w literaturze jest już dobrze znana i używana kategoria, chciałbym wiedzieć, co to jest.

cc.complexity-theory turing-machines ct.category-theory

— Saal Hardali
źródło

Sam to powiedziałeś - funkcje obliczalne.

— Yuval Filmus

@Raphael chodzi o to, że tak naprawdę nigdy nie definiujesz struktury, dopóki nie umieścisz jej w kategorii. Wtedy pozbawione są nieistotne cechy konkretnej definicji.

— Saal Hardali

@ SaalHardali Pamiętajcie, że nie wszyscy zgadzają się z obietnicą zbawienia złożoną przez teoretyków kategorii. W rzeczywistości wielu przewraca oczami.

— Raphael

@JoshuaGrochow Istnieje morfizm oznaczony

jeśli

redukuje

(lub może na odwrót), to znaczy

. Dotyczy to, na przykład, maszyn, które na każdym wejściu zatrzymują się lub nie, ale nie mają dalszych wyników.

f

$f$

T_{1}

$T_1$

T_{2}

$T_2$

f

$f$

T_{2}

$T_2$

T_{1}

$T_1$

T_{1} (x) = T_{2} (f (x))

$T_1(x) = T_2(f(x))$

— Yuval Filmus,

Poza tym: dlaczego bazy TM powinny być obiektami? Mogą to być również morfizmy.

— Martin Berger,

Odpowiedzi:

Saal Hardali wspomniał, że chce, aby kategoria maszyn Turinga wykonywała geometrię (lub przynajmniej teorię homotopii). Istnieje jednak wiele różnych sposobów osiągnięcia podobnych celów.

Istnieje bardzo silna analogia między obliczalnością a topologią. Intuicja jest taka, że zakończenie / nieterminacja jest jak przestrzeń Sierpińskiego, ponieważ zakończenie jest możliwe do zaobserwowania (tj. Otwarte), a nieterminacja nie jest (nie otwarta). Zobacz notatki z wykładu Martina Escardo Syntetyczna topologia typów danych i klasycznych przestrzeni, aby uzyskać umiarkowanie łagodne, ale wszechstronne wprowadzenie do tych pomysłów.
W obliczeniach współbieżnych i rozproszonych często warto pomyśleć o możliwych wykonaniach programu jako przestrzeni, a następnie różne ograniczenia synchronizacji można wyrazić jako homotopiczne właściwości przestrzeni. (Fakt, że egzekucja odbywa się w określonym czasie wydaje się wymagać bardziej ukierunkowanej teorii homotopii niż zwykłej teorii homotopii).

Zobacz artykuł Erica Goubaulta Niektóre geometryczne perspektywy dotyczące teorii współbieżności, aby uzyskać więcej szczegółów. Zobacz także artykuł Maurycego Herlihy i zdobywcy nagrody Nir Shavita Goedel, Topologiczna struktura asynchronicznego obliczania , w którym rozwiązano pewne długotrwałe otwarte problemy w teorii programowania rozproszonego.
Trzecia idea pochodzi od teorii typu homotopii, poprzez odkrycie, że teoria typu Martina-Löfa jest (prawdopodobnie?) Syntaktyczną prezentacją (w sensie generatorów i relacji) teorii omega-grupoidów - tj. Modeli abstrakcyjnych teoria homotopii. Najlepszym wprowadzeniem do tych pomysłów jest teoria homotopii .

Pamiętaj, że wszystkie te pomysły bardzo się od siebie różnią, ale wszystkie nadal używają intuicji geometrycznych! Są jeszcze inne, których nie znam, takie jak zastosowania w teorii złożoności geometrycznej oraz sposób, w jaki teorie obwodów można opisać w kategoriach (ko) homologii grafów .

Zasadniczo, gdy wykonujesz CS, geometria jest narzędziem - używasz go do sformalizowania intuicji, abyś mógł uzyskać efekt dzięki ogromnemu nakładowi pracy, który został na nim wykonany. Ale to wzmacniacz pomysłów, nie zastępujący pomysłów!

— Neel Krishnaswami
źródło

Jeśli twoje obiekty to maszyny Turinga, istnieje kilka rozsądnych możliwości morfizmów. Na przykład:

1) Rozważ maszyny Turinga jako automaty i rozważ zwykłe morfizmy automatów (mapy między alfabetami a stanami, które są ze sobą zgodne), które albo zachowują ruchy głowicy (głowic) taśmy, albo dokładnie odwracają się je (np. za każdym razem, gdy źródłowa TM idzie w lewo, docelowa TM idzie w prawo i odwrotnie).

2a) Rozważ symulacje lub bisimulacje .

$T_1$ $T_2$ $f$ $T_1(x) = T_2(f(x))$ $x$ .

3) Rozważ wykres przejścia maszyny Turinga (każdy wierzchołek to pełny opis stanu maszyny i taśm, z ukierunkowanymi krawędziami odpowiadającymi przejściom, które wykonałaby TM) i rozważ morfizmy wykresów. W przypadku baz TM jest to jednak bardzo gruba zależność, ponieważ zasadniczo ignoruje lokalny charakter obliczeń (ignoruje na przykład, jaka jest zawartość taśm).

Myślę, że prawdziwe pytanie brzmi: co chcesz wiedzieć o bazach TM lub co z nimi zrobić ? W przypadku braku tego trudno jest argumentować za jedną definicją nad drugą, poza naturą (w zwykłym znaczeniu tego słowa, a nie kategorycznym).

— Joshua Grochow
źródło

Jestem bardzo nowy w tego rodzaju matematyce. Czytałem w przeszłości o teorii złożoności, ale dopiero niedawno ją podniosłem po tym, jak zobaczyłem kogoś w Internecie, twierdzącego, że w jakiś sposób techniki kohomologiczne wejdą w teorię złożoności w następnym stuleciu i zainteresowało mnie to. Po przeczytaniu zrozumiałem, że poza powierzchownym zrozumieniem definicji maszyny Turinga, w zasadzie nie mam pojęcia, co dokładnie koduje. Tak doszedłem do pytania. Można więc powiedzieć, że na bardzo podstawowym poziomie próbuję sobie wyobrazić, jak kohomologia może wejść w teorię złożoności.

— Saal Hardali

Zdaję sobie sprawę, że jest to wyjątkowo przedwczesne dla kogoś takiego jak ja, który bardzo mało rozumie na ten temat, a mimo to chciałem trochę pogodzić się z tym pomysłem w głowie „robienia teorii homotopii w kategorii maszyn Turinga”. Twoja odpowiedź jest miła iz pewnością staram się przeczytać więcej o jej aspektach. Dziękuję Ci.

— Saal Hardali,

@ SaalHardali: Jestem ciekawy, gdzie przeczytałeś, że kohomologia wejdzie w teorię złożoności? Mogę myśleć na dwa sposoby, ale nie widzę jeszcze trasy według teorii typu homotopii (być może dlatego, że jeszcze nie rozumiem HoTT wystarczająco dobrze). Dwa sposoby, które widzę: (1) to już się stało, mianowicie. Herlihy i Rajsbaum oraz (2) poprzez geometryczną teorię złożoności.

— Joshua Grochow

Teorią homotopii odwoływałem się do ogólnej idei badania kategorii o słabych równoważnikach i nie tyle HoTT. Przeczytałem go w ankiecie na temat P =? NP. Nietrudno go znaleźć. Myślę, że był on powiązany z jednym z pytań na tej stronie. Wydaje mi się, że moim pierwszym przypuszczeniem (jako outsider) było to, że może istnieje jakiś interesujący słaby ekwiwalent w jakiejś kategorii modelu obliczeń, który w jakiś sposób odpowiada klasom złożoności, a następnie badanie funktorów niezmienniczych przy tych słabych ekwiwalentach będzie stanowić coś, co nazywam „ teoria homotopii ”jest to jednak prawdopodobnie bardzo naiwna i całkowita miss.

— Saal Hardali,

Jeśli interesujesz się teorią złożoności, a nie teorią obliczalności, być może ta odpowiedź jest dla Ciebie pomocna: cstheory.stackexchange.com/a/3422/4896

— Sasho Nikolov

Mogą Cię zainteresować kategorie Turinga autorstwa Robina Cocketta i Pietera Hofstry. Z punktu widzenia teorii kategorii na pytanie „co to jest kategorii maszyny Turinga” jest mniej interesująca niż „co jest kategoryczny struktura, która stanowi podstawę obliczenia”. W ten sposób Robin i Pieter określają ogólny rodzaj kategorii, która jest odpowiednia do opracowania teorii obliczalności. Następnie istnieje kilka możliwości zdefiniowania takiej kategorii, zaczynając od maszyn Turinga. Po co mieć jedną kategorię, skoro można mieć całą kategorię?

— Andrej Bauer
źródło