Problem stopu

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Problem stopu – zagadnienie algorytmiczne odpowiadające, dla danego algorytmu, na pytanie, czy realizujący go program zatrzyma się (w skończonym czasie); pytanie może dotyczyć konkretnych danych wejściowych albo wszystkich możliwych. O programie, który zatrzymuje się dla wszystkich możliwych danych mówi się, że ma własność stopu.

Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: istnieje algorytm, który oblicza odpowiedź na dowolne pytanie stawiane przez problem.David Elieser Deutsch (ur. 1953 w Hajfie, Izrael) – fizyk Uniwersytetu w Oksfordzie, członek Towarzystwa Królewskiego w Londynie.

Problem stopu bywa trudny do rozstrzygnięcia, przykładem może być sformułowany w prosty sposób problem Collatza, dla którego odpowiedź jest dotychczas nieznana.

Nierozstrzygalność[ | edytuj kod]

 Zapoznaj się również z: rozstrzygalność.

Nie istnieje uniwersalny algorytm (dla standardowej maszyny Turinga) rozstrzygający problem stopu dla wszystkich algorytmów. Jest to więc problem nierozstrzygalny. Otóż jeżeli istniałby taki program stop, to mógłby on działać zgodnie z poniższym pseudokodem:

Definicja intuicyjna: Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej „głowicy”, wykonującej proste operacje na zapisanych na taśmie wartościach.Twierdzenie Gödla to jeden z najbardziej znanych rezultatów logiki matematycznej. W istocie znane są dwa różne twierdzenia Gödla: pierwsze z nich to twierdzenie o niezupełności, drugie zaś to jego wniosek nazywany też twierdzeniem o niedowodliwości niesprzeczności. Oba twierdzenia zostały udowodnione w 1931 roku przez austriackiego matematyka i logika Kurta Gödla. Uważa się również, że twierdzenia te dają negatywną odpowiedź na drugi problem Hilberta, i w ten sposób mają spore znaczenie w filozofii matematyki. Oprócz rozpatrywanych w tym artykule twierdzeń, Gödel udowodnił też twierdzenie o istnieniu modelu i twierdzenie o nierozstrzygalności (patrz: teoria, struktura matematyczna).
procedura stop(program, dane): 
   jeżeli program(dane) zatrzymuje się, to
      zwróć tak,
   w przeciwnym przypadku
      zwróć nie.

Dla dowolnego programu program i jego danych wejściowych dane program stop zatrzymuje się, po czym zwraca tak w przypadku, gdy program wykonany wejściem dane zatrzymuje się, oraz zwraca nie w przeciwnym przypadku. Korzystając z programu stop można by jednak stworzyć nowy program test, który dla dowolnego programu program zatrzymuje się wtedy i tylko wtedy, kiedy program zapętla się na swoim własnym kodzie podanym jako dane wejściowe; jego pseudokod miałby postać:

arXiv (duże X w nazwie reprezentuje grecką literę χ (chi), nazwę należy więc czytać ‘archiv’) – elektroniczne archiwum naukowych preprintów. Gromadzi artykuły z następujących dziedzin: fizyki z astronomią, matematyki, informatyki, statystyki i biologii (quantitative biology) i matematyki finansowej. Archiwum powstało w roku 1991 w Los Alamos National Laboratory, początkowo dostępne było pod adresem xxx.lanl.gov. Obecnie funkcjonuje przy Uniwersytecie Cornella. Pseudokodem nazywany jest taki sposób zapisu algorytmu, który, zachowując strukturę charakterystyczną dla kodu zapisanego w języku programowania, rezygnuje ze ścisłych reguł składniowych na rzecz prostoty i czytelności. Pseudokod nie zawiera szczegółów implementacyjnych (jak np. inicjalizacja zmiennych, alokacja pamięci), często też opuszcza się w nim opis działania podprocedur (jeśli powinien być on oczywisty dla czytelnika), zaś nietrywialne kroki algorytmu opisywane są z pomocą formuł matematycznych lub zdań w języku naturalnym.
procedura test(program): 
   jeżeli stop(program, program) = tak, to
      zapętl się.

Powstaje wtedy pytanie: czy program test zatrzymuje się po otrzymaniu swojego własnego kodu jako danych wejściowych (czyli po wywołaniu test(test))?

  • Jeżeli wywołanie zapętli się, to stop zwróci nie, czyli procedura test zatrzyma się, co przeczy założeniom o zapętleniu się wywołania test(test)
  • Jeżeli wywołanie zatrzyma się, to stop zwróci tak, czyli procedura test zapętli się, co przeczy założeniom o zatrzymaniu się wywołania test(test) oraz o rozstrzygalności problemu stopu przez procedurę stop;
  • Powyższy dowód nie wprost zaprowadził nas do sprzeczności z początkowymi założeniami, z czego wynika, iż nie istnieje taki uniwersalny algorytm, który rozstrzyga problem stopu dla dowolnego algorytmu.

    Problem nierozstrzygalny – w teorii obliczeń – problem decyzyjny, dla którego nie istnieje algorytm, który po skończonej liczbie kroków jednoznacznie odpowie tak lub nie dla dowolnych danych wejściowych.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

    Zobacz też[ | edytuj kod]

  • twierdzenie Gödla
  • pracowity bóbr
  • Przypisy[ | edytuj kod]

    1. Udowodniono, że taki algorytm istnieje, jeśli maszyna Turinga ma dostęp do zamkniętych krzywych czasopodobnych w wersji Deutscha (Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini, Computability Theory of Closed Timelike Curves, „arXiv [quant-ph]”, 18 września 2016, arXiv:1609.05507 [dostęp 2019-09-30].) albo kwantowej podpowiedzi i aparatury pomiarowej nie powodującej kolapsu funkcji falowej (Scott Aaronson, PDQP/qpoly = ALL, „arXiv [quant-ph]”, 22 maja 2018, arXiv:1805.08577 [dostęp 2019-09-30].).
    Kontrola autorytatywna – w terminologii bibliotekoznawczej określenie procedur zapewniających utrzymanie w sposób konsekwentny haseł (nazw, ujednoliconych tytułów, tytułów serii i haseł przedmiotowych) w katalogach bibliotecznych przez zastosowanie wykazu autorytatywnego zwanego kartoteką wzorcową.Oprogramowanie (ang. software) – całość informacji w postaci zestawu instrukcji, zaimplementowanych interfejsów i zintegrowanych danych przeznaczonych dla komputera do realizacji wyznaczonych celów. Celem oprogramowania jest przetwarzanie danych w określonym przez twórcę zakresie. Oprogramowanie to dział informatyki. Oprogramowanie jest synonimem terminów program komputerowy oraz aplikacja, przy czym stosuje się go zazwyczaj do określania większych programów oraz ich zbiorów.




    Warto wiedzieć że... beta

    Gemeinsame Normdatei (GND) – kartoteka wzorcowa, stanowiąca element centralnego katalogu Niemieckiej Biblioteki Narodowej (DNB), utrzymywanego wspólnie przez niemieckie i austriackie sieci biblioteczne.

    Reklama