Nierozstrzygnięty problem - Undecidable problem
W teorii obliczalności i teorii złożoności obliczeniowej , problem nierozstrzygalny jest problem decyzyjny , dla których jest to okazało się niemożliwe, aby skonstruować algorytm , który zawsze prowadzi do prawidłowego tak lub nie odpowiedź. Przykładem jest problem zatrzymania : można udowodnić, że nie ma algorytmu, który poprawnie określa, czy dowolne programy w końcu zatrzymają się po uruchomieniu.
Tło
Problem decyzyjny to dowolne pytanie typu „tak lub nie” dotyczące nieskończonego zestawu danych wejściowych. Z tego powodu tradycyjnie definiuje się problem decyzyjny równoważnie jako zbiór danych wejściowych, dla których problem zwraca yes . Wejścia te mogą być liczbami naturalnymi, a także inne wartości innego rodzaju, takie jak ciągi o języku formalnym . Używając pewnego kodowania, takiego jak numeracja Gödla , łańcuchy mogą być zakodowane jako liczby naturalne. Zatem problem decyzyjny nieformalnie sformułowany w terminach języka formalnego jest również równoważny zbiorowi liczb naturalnych . Aby formalna definicja była prosta, jest ona sformułowana w kategoriach podzbiorów liczb naturalnych.
Formalnie problem decyzyjny jest podzbiorem liczb naturalnych. Odpowiadający temu nieformalny problem polega na rozstrzygnięciu, czy dana liczba znajduje się w zestawie. Problem decyzyjny A nazywa się rozstrzygalnym lub skutecznie rozwiązywalnym, jeśli A jest zbiorem rekurencyjnym, a w przeciwnym razie nierozstrzygalny. Problem jest nazywany częściowo rozstrzygalnym, półrozstrzygalnym, rozwiązywalnym lub dowodliwym, jeśli A jest zbiorem rekurencyjnie przeliczalnym .
Przykład: problem zatrzymania w teorii obliczalności
W teorii obliczalności The zatrzymanie problemem jest problem decyzyjny , który można sformułować następująco:
- Mając opis dowolnego programu i skończone dane wejściowe, zdecyduj, czy program zakończy działanie, czy będzie działał bez końca.
Alan Turing udowodnił w 1936 r., że ogólny algorytm działający na maszynie Turinga, który rozwiązuje problem zatrzymania dla wszystkich możliwych par program-wejście, koniecznie nie może istnieć. Stąd problem zatrzymania jest nierozstrzygnięty dla maszyn Turinga.
Związek z twierdzeniem o niezupełności Gödla
Koncepcje podniesione przez twierdzenia o niezupełności Gödla są bardzo podobne do tych podniesionych przez problem zatrzymania, a dowody są dość podobne. W rzeczywistości słabsza forma Pierwszego Twierdzenia o Niezupełności jest łatwą konsekwencją nierozstrzygalności problemu zatrzymania. Ta słabsza forma różni się od standardowego stwierdzenia twierdzenia o niezupełności twierdzeniem, że aksjomatyzacja liczb naturalnych, która jest zarówno pełna, jak i poprawna, jest niemożliwa. Część „dźwiękowa” to osłabienie: oznacza to, że wymagamy, aby dany system aksjomatyczny dowodził tylko prawdziwych twierdzeń o liczbach naturalnych. Ponieważ solidność implikuje spójność , ta słabsza forma może być postrzegana jako następstwo formy silnej. Należy zauważyć, że twierdzenie standardowej postaci Pierwszego Twierdzenia o Niezupełności Gödla nie jest całkowicie związane z wartością prawdziwości twierdzenia, a dotyczy jedynie kwestii, czy można je znaleźć za pomocą dowodu matematycznego .
Słabszą postać twierdzenia można wykazać z nierozstrzygalności problemu zatrzymania w następujący sposób. Załóżmy, że mamy solidną (a więc spójną) i pełną aksjomatyzację wszystkich prawdziwych zdań logicznych pierwszego rzędu o liczbach naturalnych . Następnie możemy zbudować algorytm, który wylicza wszystkie te stwierdzenia. Oznacza to, że istnieje algorytm N ( n ), który przy danej liczbie naturalnej n oblicza prawdziwe zdanie logiki pierwszego rzędu dotyczące liczb naturalnych i że dla wszystkich prawdziwych zdań istnieje co najmniej jedno n takie, że N ( n ) daje to stwierdzenie. Załóżmy teraz, że chcemy, aby zdecydować, czy algorytm z reprezentacją ciągu postojów na wejściu í . Wiemy, że to zdanie można wyrazić za pomocą zdania logiki pierwszego rzędu, powiedzmy H ( a , i ). Od aksjomatyzacji zakończeniu wynika, że gdy istnieją n taki sposób, że N ( n ) = H ( , I ), lub nie jest N ' , tak że N ( n ) = Ź H ( , I ). Więc jeśli będziemy iterować przez wszystkie n, aż znajdziemy H ( a , i ) lub jego negację, zawsze zatrzymamy się, a ponadto odpowiedź, którą nam udzieli, będzie prawdziwa (przez rozsądek). Oznacza to, że daje nam to algorytm do rozstrzygania problemu zatrzymania. Ponieważ wiemy, że taki algorytm nie może istnieć, wynika z tego, że założenie, że istnieje spójna i pełna aksjomatyzacja wszystkich prawdziwych zdań logicznych pierwszego rzędu o liczbach naturalnych, musi być fałszywe.
Przykłady nierozstrzygalnych problemów
Problemy nierozstrzygalne mogą dotyczyć różnych tematów, takich jak logika , abstrakcyjne maszyny czy topologia . Ponieważ istnieje niezliczona ilość nierozstrzygalnych problemów, każda lista, nawet o nieskończonej długości , jest z konieczności niekompletna.
Przykłady nierozstrzygalnych stwierdzeń
We współczesnym użyciu istnieją dwa różne znaczenia słowa „nierozstrzygalny”. Pierwszym z nich jest sens używany w odniesieniu do twierdzeń Gödla, że zdanie nie jest ani dowodliwe, ani obalalne w określonym systemie dedukcyjnym . Drugi sens jest używany w odniesieniu do teorii obliczalności i odnosi się nie do twierdzeń, ale do problemów decyzyjnych , które są policzalnie nieskończonymi zestawami pytań, z których każdy wymaga odpowiedzi tak lub nie. Mówi się, że taki problem jest nierozstrzygalny, jeśli nie ma obliczalnej funkcji, która poprawnie odpowiada na każde pytanie w zestawie problemów. Związek między tymi dwoma jest taki, że jeśli problem decyzyjny jest nierozstrzygalny (w sensie teoretycznym rekurencji), to nie ma spójnego, efektywnego systemu formalnego, który dowodzi dla każdego pytania A w problemie albo „odpowiedź na A jest tak” albo odpowiedź na A brzmi nie".
Ze względu na dwa znaczenia słowa nierozstrzygalny, termin niezależny jest czasami używany zamiast nierozstrzygalny w znaczeniu „ani do udowodnienia, ani do obalenia”. Użycie słowa „niezależny” jest jednak również niejednoznaczne. Może to oznaczać po prostu „nie do udowodnienia”, pozostawiając otwartą kwestię, czy niezależne oświadczenie może zostać obalone.
Nierozstrzygalność zdania w konkretnym systemie dedukcyjnym sama w sobie nie odpowiada na pytanie, czy wartość logiczna zdania jest dobrze zdefiniowana, czy też może być określona innymi sposobami. Nierozstrzygalność oznacza jedynie, że rozważany konkretny system dedukcyjny nie dowodzi prawdziwości lub fałszywości twierdzenia. To, czy istnieją tak zwane „absolutnie nierozstrzygalne” twierdzenia, których wartość prawdy nigdy nie może być poznana lub jest źle określona, jest kwestią kontrowersyjną wśród różnych szkół filozoficznych .
Jednym z pierwszych problemów, co do których podejrzewano, że są nierozstrzygalne, w drugim znaczeniu tego słowa, był problem słowny dla grup , po raz pierwszy postawiony przez Maxa Dehna w 1911 r., który pyta, czy istnieje skończenie przedstawiona grupa, dla której nie istnieje algorytm pozwalający określić, czy dwa słowa są równoważne. Wykazano, że tak było w 1952 roku.
Połączona praca Gödla i Paula Cohena dała dwa konkretne przykłady twierdzeń nierozstrzygalnych (w pierwszym znaczeniu tego terminu): Hipotezy continuum nie można ani udowodnić, ani obalić w ZFC (standardowa aksjomatyzacja teorii mnogości ) i aksjomat wybór nie może być ani udowodniony, ani obalony w ZF (co jest wszystkimi aksjomatami ZFC z wyjątkiem aksjomatu wyboru). Te wyniki nie wymagają twierdzenia o niezupełności. Gödel udowodnił w 1940 roku, że żadne z tych stwierdzeń nie może być obalone w teorii mnogości ZF lub ZFC. W latach 60. Cohen udowodnił, że żadnego z nich nie można udowodnić na podstawie ZF, a hipotezy kontinuum nie można udowodnić na podstawie ZFC.
W 1970 roku rosyjski matematyk Jurij Matiyasevich pokazał, że Dziesiąty Problem Hilberta , postawiony w 1900 roku jako wyzwanie dla matematyków następnego stulecia, nie może być rozwiązany. Wyzwanie Hilberta szukało algorytmu, który znajduje wszystkie rozwiązania równania diofantycznego . Równanie diofantyczne jest bardziej ogólnym przypadkiem Wielkiego Twierdzenia Fermata ; Szukamy korzeni całkowitych : a wielomian w dowolnej liczbie zmiennych o współczynnikach całkowitych. Ponieważ mamy tylko jedno równanie, ale n zmiennych, istnieje nieskończenie wiele rozwiązań (i łatwo je znaleźć) na płaszczyźnie zespolonej ; jednak problem staje się niemożliwy, jeśli rozwiązania są ograniczone tylko do wartości całkowitych. Matiyasevich wykazał, że problem ten jest nierozwiązywalny, mapując równanie diofantyczne na rekurencyjnie przeliczalny zbiór i powołując się na twierdzenie o niezupełności Gödla.
W 1936 roku Alan Turing udowodnił, że problem zatrzymania — pytanie, czy maszyna Turinga zatrzymuje się na danym programie — jest nierozstrzygalny w drugim znaczeniu tego terminu. Wynik ten został później uogólniony przez twierdzenie Rice'a .
W 1973 Saharon Shelah wykazał, że problem Whiteheada w teorii grup jest nierozstrzygalny, w pierwszym znaczeniu tego terminu, w standardowej teorii zbiorów.
W 1977 Paris i Harrington udowodnili, że zasada Parisa-Harringtona , wersja twierdzenia Ramseya , jest nierozstrzygalna w aksjomatyzacji arytmetyki podanej przez aksjomaty Peano, ale można dowieść, że jest prawdziwa w szerszym systemie arytmetyki drugiego rzędu .
Twierdzenie Kruskala o drzewie , które ma zastosowanie w informatyce, jest również nierozstrzygalne z aksjomatów Peano, ale można je udowodnić w teorii mnogości. W rzeczywistości twierdzenie Kruskala (lub jego skończona forma) jest nierozstrzygalne w znacznie silniejszym systemie, który kodyfikuje zasady akceptowane na podstawie filozofii matematyki zwanej predykatywizmem.
Twierdzenie Goodsteina jest stwierdzeniem o teorii liczb naturalnych Ramseya, którą Kirby i Paris wykazali jako nierozstrzygalną w arytmetyce Peano.
Gregory Chaitin stworzył nierozstrzygalne twierdzenia w algorytmicznej teorii informacji i udowodnił w tym kontekście kolejne twierdzenie o niezupełności. Twierdzenie Chaitina mówi, że dla każdej teorii, która może reprezentować wystarczająco dużo arytmetyki, istnieje górna granica c, tak że nie można udowodnić w tej teorii określonej liczby, aby złożoność Kołmogorowa była większa niż c . Podczas gdy twierdzenie Gödla jest powiązane z paradoksem kłamcy , wynik Chaitina jest powiązany z paradoksem Berry'ego .
W 2007 roku badacze Kurtz i Simon, opierając się na wcześniejszych pracach JH Conwaya z lat 70., wykazali, że naturalne uogólnienie problemu Collatza jest nierozstrzygnięte.