Teoria obliczalności - Computability theory

Dla pojęcia obliczalności, zobacz obliczalności .

Teoria obliczalności , znana również jako teoria rekurencji , jest gałęzią logiki matematycznej , informatyki i teorii obliczeń, która powstała w latach 30. XX wieku w badaniach nad funkcjami obliczalnymi i stopniami Turinga . Od tego czasu dziedzina została rozszerzona o badanie uogólnionej obliczalności i definiowalności. W tych obszarach teoria obliczalności pokrywa się z teorią dowodu i efektywną opisową teorią mnogości .

Podstawowe pytania poruszane przez teorię obliczalności obejmują:

  • Co to znaczy, że funkcja na liczbach naturalnych jest obliczalna?
  • Jak można sklasyfikować funkcje nieobliczalne w hierarchię na podstawie ich poziomu nieobliczalności?

Chociaż istnieje znaczne nakładanie się wiedzy i metod, teoretycy obliczalności matematycznej badają teorię obliczalności względnej, pojęcia redukowalności i struktury stopni; ci w dziedzinie informatyki koncentrują się na teorii hierarchii subrekurencyjnych , metodach formalnych i językach formalnych .

Zbiory obliczalne i nieobliczalne

Teoria obliczalności powstała w latach 30. XX wieku dzięki pracom Kurta Gödla , Alonzo Church , Rózsy Péter , Alana Turinga , Stephena Kleene i Emila Posta .

Podstawowe wyniki, które uzyskali badacze, ustaliły obliczalność Turinga jako prawidłową sformalizowanie nieformalnej idei efektywnego obliczania. Wyniki te doprowadziły Stephena Kleene'a (1952) do ukucia dwóch nazw „Teza Kościoła” (Kleene 1952:300) i „Teza Turinga” (Kleene 1952:376). Obecnie często traktuje się je jako jedną hipotezę, tezę Churcha-Turinga , która mówi, że każda funkcja obliczalna przez algorytm jest funkcją obliczalną . Choć początkowo sceptyczny, do 1946 roku Gödel argumentował za tą tezą:

„Tarski podkreślił w swoim wykładzie (i myślę słusznie) duże znaczenie pojęcia ogólnej rekursywności (lub obliczalności Turinga). Wydaje mi się, że znaczenie to w dużej mierze wynika z faktu, że przy tym pojęciu czasowi udało się nadać absolutne pojęcie interesującemu pojęciu epistemologicznemu, tj. takiemu, które nie zależy od wybranego formalizmu” (Gödel 1946 w Davis 1965:84).

Z definicji kalkulacji efektywnej pojawiły się pierwsze dowody, że istnieją problemy w matematyce, które nie mogą być skutecznie zdecydowali . Church (1936a, 1936b) i Turing (1936), zainspirowani technikami stosowanymi przez Gödla (1931) do udowodnienia jego twierdzeń o niezupełności, niezależnie wykazali, że problem Entscheidungs nie jest skutecznie rozstrzygalny. Wynik ten pokazał, że nie ma procedury algorytmicznej, która mogłaby poprawnie rozstrzygnąć, czy dowolne twierdzenia matematyczne są prawdziwe, czy fałszywe.

Wykazano, że wiele problemów matematycznych jest nierozstrzygniętych po ustaleniu tych początkowych przykładów. W 1947 roku Markov i Post opublikowali niezależne artykuły pokazujące, że problem tekstowy dla półgrup nie może być skutecznie rozstrzygnięty. Rozszerzając ten wynik, Piotr Nowikow i William Boone pokazali niezależnie w latach 50. XX wieku, że problem słowny dla grup nie jest skutecznie rozwiązywalny: nie ma skutecznej procedury, która przy danym słowie w skończenie przedstawionej grupie zadecyduje, czy element reprezentowany przez słowo jest elementem tożsamości grupy. W 1970 roku Yuri Matiyasevich udowodnił (wykorzystując wyniki Julii Robinson ) twierdzenie Matiyasevicha , z którego wynika, że dziesiąty problem Hilberta nie ma skutecznego rozwiązania; ten problem zadał pytanie, czy istnieje skuteczna procedura rozstrzygania, czy równanie diofantyczne nad liczbami całkowitymi ma rozwiązanie w liczbach całkowitych. Lista problem nierozstrzygalny daje dodatkowe przykłady problemów bez rozwiązania obliczeniowego.

Badanie, które konstrukcje matematyczne mogą być skutecznie wykonywane, jest czasami nazywane matematyką rekurencyjną ; Handbook rekurencyjnych Mathematics (Ershov i wsp. 1998) obejmuje wiele znanych wyniki w tej dziedzinie.

Obliczalność Turinga

Główna forma obliczalności badana w teorii obliczalności została wprowadzona przez Turinga (1936). Mówi się, że zbiór liczb naturalnych jest zbiorem obliczalnym (zwanym również zbiorem rozstrzygalnym , rekurencyjnym lub obliczalnym Turinga ), jeśli istnieje maszyna Turinga, która przy danej liczbie n zatrzymuje się z wyjściem 1, jeśli n jest w zbiorze i zatrzymuje się z wyjściem 0, jeśli n nie ma w zestawie. Funkcja F z liczb naturalnych, na numery fizyczne jest (Turinga) obliczeniowy , lub funkcji rekurencyjnej jeśli jest maszyna Turinga, że na wejściu N , zatrzymanie i wraca wyjściowy F ( N ). Użycie maszyn Turinga nie jest tutaj konieczne; istnieje wiele innych modeli obliczeń, które mają taką samą moc obliczeniową jak maszyny Turinga; na przykład funkcje rekurencyjne μ uzyskane z pierwotnej rekurencji i operatora μ.

Terminologia funkcji i zbiorów obliczalnych nie jest w pełni ustandaryzowana. Definicja w terminach funkcji μ-rekurencyjnych, jak również inna definicja funkcji rekursywnych przez Gödla, doprowadziła do tradycyjnej nazwy rekurencyjnej dla zbiorów i funkcji obliczanych przez maszynę Turinga. Słowo rozstrzygalność pochodzi od niemieckiego słowa Entscheidungsproblem, które było używane w oryginalnych pracach Turinga i innych. We współczesnym użyciu termin „funkcja obliczalna” ma różne definicje: według Cutlanda (1980) jest to częściowa funkcja rekurencyjna (która może być niezdefiniowana dla niektórych danych wejściowych), podczas gdy według Soare (1987) jest to funkcja całkowicie rekurencyjna ( równoważnie, ogólna funkcja rekurencyjna). Ten artykuł jest zgodny z drugą z tych konwencji. Soare (1996) podaje dodatkowe uwagi dotyczące terminologii.

Nie każdy zbiór liczb naturalnych jest obliczalny. Zatrzymanie problemem , który jest zbiorem (opisy) Maszyny że zatrzymanie na wejściu 0, jest dobrze znanym przykładem nie dający zestawu Turinga. Istnienie wielu zbiorów nieobliczalnych wynika z faktu, że maszyn Turinga jest tylko przeliczalnie wiele , a więc zbiorów obliczalnych tylko przeliczalnie wiele, ale zgodnie z twierdzeniem Cantora zbiorów liczb naturalnych jest niepoliczalnie wiele .

Chociaż problem zatrzymania nie jest obliczalny, możliwe jest symulowanie wykonywania programu i tworzenie nieskończonej listy programów, które się zatrzymują. Zatem problem zatrzymania jest przykładem zbioru przeliczalnego (ce) , który jest zbiorem, który może być wyliczony przez maszynę Turinga (inne terminy na przeliczalny przeliczalny obejmują rekursywnie przeliczalne i półrozstrzygalne ). Równoważnie zbiór jest ce wtedy i tylko wtedy, gdy jest zakresem jakiejś funkcji obliczalnej. Zbiory ce, chociaż generalnie nierozstrzygalne, zostały szczegółowo zbadane w teorii obliczalności.

Obszary badań

Poczynając od opisanej powyżej teorii zbiorów i funkcji obliczalnych, dziedzina teorii obliczalności rozrosła się i obejmuje badanie wielu ściśle powiązanych tematów. Nie są to niezależne obszary badań: każdy z tych obszarów czerpie idee i wyniki z innych, a większość teoretyków obliczalności zna większość z nich.

Obliczalność względna i stopnie Turinga

Główne artykuły: redukcja Turinga i stopień Turinga

Teoria obliczalności w logice matematycznej tradycyjnie skupiała się na obliczalności względnej , uogólnieniu obliczalności Turinga zdefiniowanej za pomocą maszyn Turinga wyroczni , wprowadzonej przez Turinga (1939). Wyrocznia Maszyna Turinga to hipotetyczne urządzenie, które oprócz wykonywania czynności zwykłej maszyny Turinga jest w stanie zadawać pytania wyroczni , która jest określonym zbiorem liczb naturalnych. Maszyna wyroczni może zadawać tylko pytania typu „Czy n jest w zestawie wyroczni?”. Na każde pytanie natychmiast odpowiemy poprawnie, nawet jeśli zestaw wyroczni nie jest obliczalny. W ten sposób maszyna wyrocznia z wyrocznią nieobliczalną będzie w stanie obliczyć zbiory, których maszyna Turinga bez wyroczni nie może.

Nieformalnie zbiór liczb naturalnych A jest redukowalny przez Turinga do zbioru B, jeśli istnieje maszyna wyrocznia, która poprawnie mówi, czy liczby znajdują się w A, gdy jest uruchamiana z B jako zbiorem wyroczni (w tym przypadku mówi się również , że zbiór A jest zbiorem wyroczni ( względnie ) obliczalne z B i rekurencyjne w B ). Jeśli zbiór A jest redukowalny przez Turinga do zbioru B, a B jest redukowalny przez Turinga do A, to mówi się, że zbiory mają ten sam stopień Turinga (zwany również stopniem nierozwiązywalności ). Stopień Turinga zbioru daje dokładną miarę tego, jak nieobliczalny jest zbiór.

Naturalne przykłady zbiorów, które nie są obliczalne, w tym wiele różnych zbiorów, które kodują warianty problemu zatrzymania , mają dwie wspólne właściwości:

  1. Są przeliczalne i
  2. Każdy z nich można przełożyć na dowolny inny poprzez redukcję wiele-jedną . Oznacza to, że przy takich zbiorach A i B istnieje całkowicie obliczalna funkcja f taka, że A = { x  : f ( x ) ∈ B }. Mówi się, że te zestawy są równoważne wiele-jeden (lub ekwiwalent m ).

Redukcje wiele-jeden są „silniejsze” niż redukcje Turinga: jeśli zbiór A jest redukowalny do wielu-jeden do zbioru B , to A jest redukowalnym przez Turinga do B , ale odwrotność nie zawsze zachodzi. Chociaż naturalne przykłady zbiorów nieobliczalnych są wszystkie równoważne wiele-jeden, możliwe jest skonstruowanie przeliczalnych przeliczalnych zbiorów A i B takich, że A jest redukowalnym przez Turinga do B, ale nie jest redukowalny przez wiele-jeden do B . Można wykazać, że każdy zbiór przeliczalny przeliczalny jest sprowadzalny do wiele-jeden do problemu zatrzymania, a zatem problem zatrzymania jest najbardziej skomplikowanym zbiorem przeliczalnym przeliczalnym ze względu na redukowalność wiele-jeden i ze względu na redukowalność Turinga. Post (1944) zapytał, czy każdy przeliczalny zbiór jest albo obliczalny, albo odpowiednik Turinga równoważny problemowi zatrzymania, to znaczy, czy nie istnieje żaden zbiór przeliczalny przeliczalny ze stopniem Turinga pośrednim między tymi dwoma.

Jako wyniki pośrednie Post zdefiniował naturalne typy zestawów przeliczalnych, takich jak zestawy proste , hiperproste i hiperhiperproste. Post pokazał, że te zbiory są ściśle pomiędzy zbiorami obliczalnymi a problemem zatrzymania w odniesieniu do redukowalności wiele-jeden. Post pokazał również, że niektóre z nich są ściśle pośrednie w stosunku do innych pojęć redukowalności silniejszych niż redukowalność Turinga. Ale Post pozostawił otwarty główny problem istnienia przeliczalnych zbiorów o pośrednim stopniu Turinga; problem ten stał się znany jako problem Posta . Po dziesięciu latach Kleene i Post wykazali w 1954 r., że istnieją pośrednie stopnie Turinga między stopniami ze zbiorów obliczalnych a problemem zatrzymania, ale nie wykazali, że którykolwiek z tych stopni zawiera zbiór przeliczalny. Wkrótce potem Friedberg i Muchnik niezależnie rozwiązali problem Posta, ustalając istnienie przeliczalnych zbiorów pośrednich stopni. Ten przełomowy wynik otworzył szerokie badania stopni Turinga zbiorów przeliczalnych, które okazały się mieć bardzo skomplikowaną i nietrywialną strukturę.

Istnieje niezliczona ilość zbiorów, które nie są przeliczalne, a badanie stopni Turinga wszystkich zbiorów jest tak samo centralne w teorii obliczalności, jak badanie przeliczalnych stopni Turinga. Skonstruowano wiele stopni o specjalnych właściwościach: stopnie wolne od hiperimmunizacji, gdzie każda funkcja obliczalna względem tego stopnia jest zdominowana przez (nierelatywizowaną) funkcję obliczalną; wysokie stopnie, w stosunku do których można obliczyć funkcję f, która dominuje nad każdą obliczalną funkcją g w tym sensie, że istnieje stała c zależna od g taka, że g(x) < f(x) dla wszystkich x > c ; stopnie losowe zawierające zbiory algorytmicznie losowe ; 1-ogólne stopnie z 1-ogólnych zestawów; i stopnie poniżej problemu zatrzymania zbiorów obliczalnych granicznie .

Badanie dowolnych (niekoniecznie przeliczalnych) stopni Turinga obejmuje badanie skoku Turinga. Biorąc pod uwagę zestaw The skok Turing od A jest zbiorem liczb naturalnych kodujących rozwiązanie problemu stopu dla maszyn Turinga z systemem oracle oracle A . Skok Turinga dowolnego zestawu ma zawsze wyższy stopień Turinga niż oryginalny zestaw, a twierdzenie Friedburga pokazuje, że każdy zestaw, który oblicza problem Haltinga, można uzyskać jako skok Turinga innego zestawu. Twierdzenie Posta ustanawia ścisły związek między operacją skoku Turinga a hierarchią arytmetyczną , która jest klasyfikacją pewnych podzbiorów liczb naturalnych na podstawie ich definiowalności w arytmetyce.

Wiele ostatnich badań nad stopniami Turinga koncentrowało się na ogólnej strukturze zbioru stopni Turinga i zbioru stopni Turinga zawierających zbiory przeliczalne. Głębokie twierdzenie Shore'a i Slamana (1999) stwierdza, że ​​funkcja odwzorowująca stopień x na stopień jej skoku Turinga jest definiowalna w porządku cząstkowym stopni Turinga. Niedawne badanie przeprowadzone przez Ambos-Spies i Fejer (2006) daje przegląd tych badań i ich historycznego rozwoju.

Inne redukcje

Główny artykuł: Redukcja (teoria rekurencji)

Ciągły obszar badań w teorii obliczalności zajmuje się badaniem relacji redukowalności innych niż redukowalność Turinga. Post (1944) wprowadził kilka silnych redukowalności , nazwanych tak, ponieważ implikują one redukowalność za pomocą tabeli prawdy. Maszyna Turinga implementująca silną redukowalność obliczy całkowitą funkcję bez względu na to, z jaką wyrocznią zostanie przedstawiona. Słabe redukcje to te, w których proces redukcji może nie zakończyć się dla wszystkich wyroczni; Jednym z przykładów jest redukowalność Turinga.

Silne redukowalności obejmują:

Redukcja jeden-jeden
A jest redukowalne do jednego (lub do 1 ) do B, jeśli istnieje całkowicie obliczalna funkcja iniekcyjna f taka, że ​​każde n jest w A wtedy i tylko wtedy, gdy f ( n ) jest w B .
Redukcja wiele-jednego
Jest to w zasadzie jedno-redukowalność bez ograniczeń, że F jest za pomocą wstrzyknięć. A jest redukowalne do wielu jeden (lub m-redukowalne ) do B , jeśli istnieje całkowicie obliczalna funkcja f taka, że ​​każde n jest w A wtedy i tylko wtedy, gdy f ( n ) jest w B .
Redukcja w tabeli prawdy
A jest redukowalną tabelą prawdy do B, jeśli A jest sprowadzalną do B za pomocą wyroczni maszyny Turinga, która oblicza całkowitą funkcję niezależnie od wyroczni, którą otrzyma. Ze względu na zwartość przestrzeni Cantora jest to równoznaczne z stwierdzeniem, że redukcja przedstawia pojedynczą listę pytań (zależną tylko od danych wejściowych) jednocześnie do wyroczni, a następnie po obejrzeniu ich odpowiedzi jest w stanie wytworzyć wynik bez zadawania dodatkowych pytań niezależnie od odpowiedzi wyroczni na początkowe pytania. Zbadano również wiele wariantów redukowalności za pomocą tabeli prawdy.

Dalsze redukcje (dodatnia, dysjunktywna, koniunkcyjna, liniowa oraz ich wersje słabe i ograniczone) zostały omówione w artykule Redukcja (teoria obliczalności) .

Główne badania nad silnymi redukowalnościami polegały na porównaniu ich teorii, zarówno dla klasy wszystkich zbiorów przeliczalnych, jak i klasy wszystkich podzbiorów liczb naturalnych. Ponadto zbadano relacje między redukowalnościami. Wiadomo na przykład, że każdy stopień Turinga jest albo stopniem tabeli prawdy, albo jest połączeniem nieskończenie wielu stopni tabeli prawdy.

Badano również redukowalności słabsze niż redukowalność Turinga (to znaczy redukowalności, które są implikowane przez redukowalność Turinga). Najbardziej znane to redukowalność arytmetyczna i redukowalność hiperarytmetyczna . Te redukcje są ściśle związane z definiowalnością w standardowym modelu arytmetyki.

Twierdzenie Rice'a i hierarchia arytmetyczna

Ryż wykazały, że dla każdego nietrywialna klasy C (które zawiera kilka, ale nie wszystkie elementy Ce) zestaw indeks E = { e : the e p CE zestaw W E jest C } ma tę właściwość, że albo problemu stopu lub jego dopełnieniem jest wiele -jeden redukowalny do E , to znaczy może być odwzorowany przy użyciu redukcji wiele-jeden do E ( więcej szczegółów w twierdzeniu Rice'a ). Ale wiele z tych zestawów indeksów jest nawet bardziej skomplikowanych niż problem zatrzymania. Tego typu zestawy można klasyfikować za pomocą hierarchii arytmetycznej . Na przykład zbiór indeksów FIN klasy wszystkich zbiorów skończonych jest na poziomie Σ 2 , zbiór indeksów REC klasy wszystkich zbiorów rekurencyjnych jest na poziomie Σ 3 , zbiór indeksów COFIN wszystkich zbiorów koskończonych jest również na poziomie poziom Σ 3 i zbiór indeksów COMP klasy wszystkich kompletnych zbiorów Turinga Σ 4 . Te poziomy hierarchii są zdefiniowane indukcyjnie, Σ n +1 zawiera tylko wszystkie zbiory, które są przeliczalne w stosunku do Σ n ; Σ 1 zawiera zbiory przeliczalne przeliczalne. Podane tutaj zbiory indeksów są nawet kompletne dla swoich poziomów, to znaczy, że wszystkie zbiory na tych poziomach mogą być zredukowane do wielu-jeden do podanych zbiorów indeksów.

Matematyka odwrotna

Główny artykuł: matematyka odwrotna

Program matematyki odwrotnej pyta, które aksjomaty istnienia zbiorów są niezbędne do udowodnienia określonych twierdzeń matematycznych w podsystemach arytmetyki drugiego rzędu . Badanie to zostało zainicjowane przez Harveya Friedmana i zostało szczegółowo zbadane przez Stephena Simpsona i innych; Simpson (1999) szczegółowo omawia program. Omawiane aksjomaty istnienia zbioru odpowiadają nieformalnie aksjomatom mówiącym, że zbiór potęg liczb naturalnych jest zamknięty pod różnymi pojęciami redukowalności. Najsłabszym takim aksjomatem badanym w matematyce odwrotnej jest rozumienie rekurencyjne , które stwierdza, że ​​zbiór mocy naturalnych jest domknięty pod redukowalnością Turinga.

Numeracja

Numeracja to wyliczenie funkcji; ma dwa parametry, e i x oraz wyprowadza wartość e -tej funkcji w numeracji na wejściu x . Numerowanie może być częściowo obliczalne, chociaż niektóre jego elementy są funkcjami obliczalnymi w całości. Dopuszczalne numeracje to takie, na które można przetłumaczyć wszystkie inne. Numeracja Friedberg (nazwane odkrywcy) jest jedno-numeracja wszystkich funkcjach częściowych obliczeniowy; koniecznie nie jest to numeracja dopuszczalna. Późniejsze badania dotyczyły również numeracji innych klas, takich jak klasy zbiorów przeliczalnych. Goncharov odkrył na przykład klasę zbiorów przeliczalnych przeliczalnych, dla których numeracje należą do dokładnie dwóch klas ze względu na izomorfizmy obliczalne.

Metoda priorytetowa

Dalsze informacje: stopień Turinga § problem posta i metoda pierwszeństwa

Problem Posta został rozwiązany za pomocą metody zwanej metodą priorytetową ; dowód przy użyciu tej metody nazywany jest argumentem priorytetowym . Ta metoda jest używana głównie do konstruowania przeliczalnych zbiorów o określonych właściwościach. Aby użyć tej metody, pożądane właściwości zestawu, który ma zostać skonstruowany, są rozbijane na nieskończoną listę celów, zwaną wymaganiami , tak że spełnienie wszystkich wymagań spowoduje, że skonstruowany zestaw będzie miał pożądane właściwości. Każde wymaganie jest przypisane do liczby naturalnej reprezentującej priorytet wymagania; więc 0 jest przypisane do najważniejszego priorytetu, 1 do drugiego najważniejszego i tak dalej. Zbiór jest następnie konstruowany etapami, przy czym każdy etap ma na celu spełnienie jednego lub większej liczby wymagań przez dodanie liczb do zbioru lub zakazanie liczb w zbiorze, tak aby ostateczny zbiór spełnił wymaganie. Może się zdarzyć, że spełnienie jednego wymagania spowoduje, że inny stanie się niespełniony; kolejność pierwszeństwa jest używana do decydowania, co zrobić w takim przypadku.

Argumenty priorytetowe zostały wykorzystane do rozwiązania wielu problemów w teorii obliczalności i zostały sklasyfikowane w hierarchię na podstawie ich złożoności (Soare 1987). Ponieważ złożone argumenty priorytetowe mogą być techniczne i trudne do naśladowania, tradycyjnie uważano za pożądane udowodnienie wyników bez argumentów priorytetowych lub sprawdzenie, czy wyniki udowodnione za pomocą argumentów priorytetowych można również udowodnić bez nich. Na przykład Kummer opublikował artykuł o dowodzie istnienia numeracji Friedberga bez zastosowania metody pierwszeństwa.

Krata zbiorów przeliczalnych przeliczalnych

Kiedy Post zdefiniował pojęcie prostego zbioru jako zbioru ce z nieskończonym dopełnieniem niezawierającym żadnego nieskończonego zbioru ce, zaczął badać strukturę zbiorów przeliczalnych przeliczalnych objętych inkluzją. Ta siatka stała się dobrze zbadaną strukturą. zbiory obliczalne mogą być zdefiniowane w tej strukturze przez podstawowy wynik, że zbiór jest obliczalny wtedy i tylko wtedy, gdy zbiór i jego uzupełnienie są przeliczalne. Nieskończone zbiory ce mają zawsze nieskończone podzbiory obliczalne; ale z drugiej strony istnieją proste zbiory, ale nie zawsze mają nieskończony, obliczalny nadzbiór. Post (1944) wprowadził już zbiory hiperproste i hiperhiperproste; później skonstruowano zbiory maksymalne, które są zbiorami ce takimi, że każdy nadzbiór ce jest albo skończoną odmianą danego zbioru maksymalnego, albo jest współskończony. Pierwotną motywacją Posta w badaniu tej sieci było znalezienie takiego pojęcia strukturalnego, że każdy zbiór, który spełnia tę własność, nie znajduje się ani w stopniu Turinga zbiorów obliczalnych, ani w stopniu Turinga problemu zatrzymania. Post nie znalazł takiej właściwości, a rozwiązanie jego problemu zastosowało metody priorytetowe; Harrington i Soare (1991) w końcu znaleźli taką nieruchomość.

Problemy z automorfizmem

Inną ważną kwestią jest istnienie automorfizmów w strukturach obliczeniowo-teoretycznych. Jedną z tych struktur jest to, że jeden z przeliczalnych zbiorów pod wtrąceniem modulo skończonej różnicy; w tej strukturze A jest poniżej B wtedy i tylko wtedy, gdy ustawiona różnica B  -  A jest skończona. Zbiory maksymalne (zgodnie z definicją w poprzednim akapicie) mają tę właściwość, że nie mogą być automorficzne do zbiorów niemaksymalnych, to znaczy, jeśli istnieje automorfizm zbiorów przeliczalnych w ramach wspomnianej właśnie struktury, to każdy zbiór maksymalny jest odwzorowany na kolejny maksymalny zestaw. Soare (1974) wykazał, że zachodzi również odwrotność, to znaczy co dwa maksymalne zbiory są automorficzne. Zatem zbiory maksymalne tworzą orbitę, to znaczy każdy automorfizm zachowuje maksimum, a dowolne dwa zbiory maksymalne są przekształcane w siebie przez jakiś automorfizm. Harrington podał kolejny przykład własności automorficznej: własności zbiorów kreatywnych, czyli zbiorów, które są równoważne problemowi zatrzymania.

Oprócz kraty zbiorów przeliczalnych, badane są również automorfizmy dla struktury stopni Turinga wszystkich zbiorów, jak również dla struktury stopni Turinga zbiorów ce. W obu przypadkach Cooper twierdzi, że skonstruował nietrywialne automorfizmy, które odwzorowują pewne stopnie na inne stopnie; konstrukcja ta nie została jednak zweryfikowana i niektórzy koledzy uważają, że konstrukcja zawiera błędy i że pytanie, czy istnieje nietrywialny automorfizm stopni Turinga, jest nadal jednym z głównych nierozwiązanych pytań w tej dziedzinie (Slaman i Woodin 1986, Ambos-Szpiedzy i Fejer 2006).

Złożoność Kołmogorowa

Główny artykuł: złożoność Kołmogorowa

Dziedzina złożoności Kołmogorowa i losowości algorytmicznej została opracowana w latach 60. i 70. przez Chaitina, Kołmogorowa, Levina, Martina-Löfa i Solomonoffa (nazwy podano tutaj w kolejności alfabetycznej; wiele badań było niezależnych, a jedność koncepcji losowości nie był wówczas rozumiany). Główną ideą jest rozważenie uniwersalnej maszyny Turinga U i zmierzenie złożoności liczby (lub łańcucha) x jako długości najkrótszego wejścia p tak, że U ( p ) daje x . Podejście to zrewolucjonizowało wcześniejsze sposoby określania, kiedy ciąg nieskończony (odpowiednik funkcji charakterystycznej podzbioru liczb naturalnych) jest losowy, czy nie, poprzez odwołanie się do pojęcia losowości dla obiektów skończonych. Złożoność Kołmogorowa stała się nie tylko przedmiotem samodzielnych badań, ale jest również stosowana do innych przedmiotów jako narzędzie do uzyskiwania dowodów. W tej dziedzinie wciąż pozostaje wiele otwartych problemów. Z tego powodu ostatnia konferencja naukowa w tej dziedzinie odbyła się w styczniu 2007 r., a listę otwartych problemów prowadzą Joseph Miller i Andre Nies.

Obliczanie częstotliwości

Ta gałąź teorii obliczalności przeanalizowała następujące pytanie: Dla ustalonych m i n z 0 <  m  <  n , dla których funkcji A można obliczyć dla dowolnych różnych n wejść x 1 ,  x 2 , ...,  x n krotka z n liczby Y 1 , Y 2 , ..., y n , że co najmniej m równań ( x K ) = y k są prawdziwe. Takie zbiory są znane jako ( m ,  n )-zestawy rekurencyjne. Pierwszym ważnym rezultatem w tej gałęzi teorii obliczalności jest wynik Trakhtenbrota, że ​​zbiór jest obliczalny, jeśli jest ( m ,  n )-rekurencyjny dla pewnego m ,  n przy 2 m  >  n . Z drugiej strony, zbiory semirekurencyjne Jockuscha (które były już nieformalnie znane przed wprowadzeniem ich przez Jockuscha w 1968 roku) są przykładami zbioru, który jest ( m ,  n )-rekurencyjny wtedy i tylko wtedy, gdy 2 m  <  n  + 1. Jest ich niepoliczalnie wiele te zbiory, a także niektóre przeliczalne, ale nieobliczalne zbiory tego typu. Później Degtev ustanowił hierarchię zbiorów przeliczalnych, które są (1,  n  + 1)-rekurencyjne, ale nie (1,  n )-rekurencyjne. Po długiej fazie badań prowadzonych przez rosyjskich naukowców, temat ten został ponownie spopularyzowany na zachodzie dzięki tezie Beigla o zapytaniach ograniczonych, które łączyły obliczanie częstotliwości z wyżej wymienionymi redukowalnościami ograniczonymi i innymi pokrewnymi pojęciami. Jednym z głównych wyników była teoria kardynalności Kummera, która stwierdza, że ​​zbiór A jest obliczalny wtedy i tylko wtedy, gdy istnieje n takie, że jakiś algorytm wylicza dla każdej krotki n różnych liczb aż do n wielu możliwych wyborów liczności tego zbioru n liczb przecinających się z A ; te wybory muszą zawierać prawdziwą kardynalność, ale pominąć przynajmniej jedną fałszywą.

Wnioskowanie indukcyjne

Jest to część teorii uczenia się zajmująca się teorią obliczalności. Opiera się na modelu uczenia się w granicy E. Marka Golda z 1967 roku i od tego czasu rozwija coraz więcej modeli uczenia się. Ogólny scenariusz jest następujący: Czy przy danej klasie S funkcji obliczalnych istnieje uczący się (to jest funkcjonał obliczalny), który wyprowadza dane wejściowe w postaci ( f (0), f (1),..., f ( n )) hipoteza. Uczący się M uczy się funkcji f, jeśli prawie wszystkie hipotezy mają ten sam indeks e z f w odniesieniu do wcześniej uzgodnionej dopuszczalnej numeracji wszystkich funkcji obliczalnych; M uczy się S jeśli M uczy się każdego f w S . Podstawowe wyniki są takie, że wszystkie przeliczalne klasy funkcji są możliwe do nauczenia, podczas gdy klasa REC wszystkich funkcji obliczalnych nie jest możliwa do nauczenia. Rozważano wiele powiązanych modeli, a także uczenie się klas zbiorów przeliczalnych przeliczalnie na podstawie pozytywnych danych jest tematem studiowanym od pionierskiego artykułu Golda z 1967 roku.

Uogólnienia obliczalności Turinga

Teoria Obliczalność obejmuje badanie ogólnych pojęć w tej dziedzinie, takich jak arytmetyczna redukowalnością , hyperarithmetical redukowalnością i teorii α-rekursji , jak opisano przez worki (1990). Te uogólnione pojęcia obejmują redukowalności, których nie mogą wykonać maszyny Turinga, ale mimo to są naturalnymi uogólnieniami redukowalności Turinga. Badania te obejmują podejścia do badania hierarchii analitycznej, która różni się od hierarchii arytmetycznej tym , że umożliwia kwantyfikację na zbiorach liczb naturalnych oprócz kwantyfikacji na podstawie pojedynczych liczb. Obszary te są powiązane z teoriami porządków i drzew; na przykład zbiór wszystkich indeksów drzew obliczalnych (niebinarnych) bez nieskończonych gałęzi jest kompletny dla poziomu hierarchii analitycznej. Zarówno redukowalność Turinga, jak i redukowalność hiperarytmetyczna są ważne w dziedzinie efektywnej opisowej teorii mnogości . Jeszcze bardziej ogólne pojęcie stopni konstruowalności badane jest w teorii mnogości .

Ciągła teoria obliczalności

Teoria obliczalności dla obliczeń cyfrowych jest dobrze rozwinięta. Teoria Obliczalność jest mniej rozwinięte do obliczenia analogowe , które występuje w komputerze analogowym , przetwarzania sygnałów analogowych , elektroniczne analogowe , sieci neuronowe i w czasie ciągłego teorii sterowania , modelowanych równaniach różniczkowych i ciągłych systemach dynamicznych (Orponen 1997; Moore, 1996).

Związki między definiowalnością, dowodem i obliczalnością

Istnieją ścisłe związki między stopniem Turinga zbioru liczb naturalnych a trudnością (w sensie hierarchii arytmetycznej ) zdefiniowania tego zbioru za pomocą wzoru pierwszego rzędu . Jedną z takich zależności precyzuje twierdzenie Posta . Słabszy związek wykazał Kurt Gödel w dowodach jego twierdzenia o zupełności i niezupełności . Dowody Gödla pokazują, że zbiór logicznych konsekwencji efektywnej teorii pierwszego rzędu jest zbiorem przeliczalnym i że jeśli teoria jest wystarczająco silna, zbiór ten będzie nieobliczalny. Podobnie twierdzenie Tarskiego o niedefiniowalności może być interpretowane zarówno w kategoriach definiowalności, jak iw kategoriach obliczalności.

Teoria obliczalności jest również powiązana z arytmetyką drugiego rzędu , formalną teorią liczb naturalnych i zbiorów liczb naturalnych. Fakt, że pewne zbiory są obliczalne lub względnie obliczalne, często implikuje, że zbiory te można zdefiniować w słabych podsystemach arytmetyki drugiego rzędu. Program matematyki odwrotnej wykorzystuje te podsystemy do pomiaru nieobliczalności właściwej dla dobrze znanych twierdzeń matematycznych. Simpson (1999) omawia wiele aspektów arytmetyki drugiego rzędu i matematyki odwrotnej.

Dziedzina teorii dowodu obejmuje badanie arytmetyki drugiego rzędu i arytmetyki Peano , a także formalne teorie liczb naturalnych słabszych niż arytmetyka Peano. Jedną z metod klasyfikacji siły tych słabych systemów jest scharakteryzowanie, które funkcje obliczeniowe system może okazać się całkowity (patrz Fairtlough i Wainer (1998)). Na przykład, w prymitywnej arytmetyce rekurencyjnej każda obliczalna funkcja, która jest do udowodnienia całkowita, jest w rzeczywistości prymitywną rekurencyjną , podczas gdy arytmetyka Peano dowodzi, że funkcje takie jak funkcja Ackermanna , które nie są prymitywnymi rekurencyjnymi, są całkowite. Jednak nie każda całkowita funkcja obliczalna jest dowodem całkowitym w arytmetyce Peano; przykładem takiej funkcji jest twierdzenie Goodsteina .

Nazwa

Dziedzina logiki matematycznej zajmująca się obliczalnością i jej uogólnieniami od początku nazywana była „teorią rekurencji”. Robert I. Soare , wybitny badacz w tej dziedzinie, zaproponował (Soare 1996), że dziedzinę tę należy nazwać „teorią obliczalności”. Twierdzi, że terminologia Turinga używająca słowa „obliczalny” jest bardziej naturalna i szerzej rozumiana niż terminologia wykorzystująca słowo „rekurencyjne” wprowadzone przez Kleene. Wielu współczesnych badaczy zaczęło używać tej alternatywnej terminologii. Badacze ci używają również terminologii, takiej jak częściowa funkcja obliczalna i zbiór przeliczalny ( ce ) zamiast częściowej funkcji rekurencyjnej i zbiór rekurencyjnie przeliczalny ( re ) . Nie wszyscy badacze zostali jednak przekonani, jak wyjaśnili Fortnow i Simpson. Niektórzy komentatorzy twierdzą, że zarówno nazwy teoria rekurencji, jak i teoria obliczalności nie oddają faktu, że większość obiektów badanych w teorii obliczalności nie jest obliczalna.

Rogers (1967) zasugerował, że kluczową właściwością teorii obliczalności jest to, że jej wyniki i struktury powinny być niezmienne w przypadku obliczalnych bijekcji na liczbach naturalnych (sugestia ta opiera się na ideach programu Erlangen w geometrii). Pomysł polega na tym, że obliczalna bijakcja jedynie zmienia nazwy liczb w zestawie, zamiast wskazywać jakąkolwiek strukturę w zestawie, podobnie jak obrót płaszczyzny euklidesowej nie zmienia żadnego geometrycznego aspektu narysowanych na niej linii. Ponieważ dowolne dwa nieskończone zbiory obliczalne są połączone za pomocą obliczalnego bijekcji, niniejsza propozycja identyfikuje wszystkie nieskończone zbiory obliczalne (skończone zbiory obliczalne są postrzegane jako trywialne). Według Rogersa, zbiory będące przedmiotem zainteresowania teorii obliczalności to zbiory nieobliczalne, podzielone na klasy równoważności przez obliczalne bijekcje liczb naturalnych.

Profesjonalna organizacja

Główną organizacją zawodową zajmującą się teorią obliczalności jest Association for Symbolic Logic , które każdego roku organizuje kilka konferencji naukowych. Interdyscyplinarne Stowarzyszenie Badawcze Computability in Europe ( Cie ) organizuje również serię corocznych konferencji.

Zobacz też

Uwagi

Bibliografia

Teksty na poziomie licencjackim
Zaawansowane teksty
Dokumenty i kolekcje ankiet
Artykuły naukowe i kolekcje

Zewnętrzne linki