• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Rozstrzygalność

    Przeczytaj także...
    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.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.
    Paradoks (gr. parádoksos – nieoczekiwany, nieprawdopodobny) – twierdzenie logiczne prowadzące do zaskakujących lub sprzecznych wniosków. Sprzeczność ta może być wynikiem błędów w sformułowaniu twierdzenia, przyjęcia błędnych założeń, a może też być sprzecznością pozorną, sprzecznością z tzw. zdrowym rozsądkiem, np. paradoks hydrostatyczny, czy paradoks bliźniąt.

    Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: istnieje algorytm, który oblicza odpowiedź na dowolne pytanie stawiane przez problem.

    Problem może być nierozstrzygalny, jeśli jego rozstrzygalność prowadziłaby do powstania paradoksów.

    Przykłady z dziedziny informatyki[]

    Nierozstrzygalność problemu stopu[]

     Osobny artykuł: Problem stopu.

    Nierozstrzygalność problemu równoważności dla ]

    Wyobraźmy sobie, że istnieje algorytm w postaci λ-wyrażenia E rozstrzygający czy dwa λ-wyrażenia są równoważne: algorytm bierze cztery wyrażenia, po czym zwraca trzecie, jeśli dwa pierwsze są równoważne, lub czwarte w przeciwnym wypadku.

    Jeśli zwróci true, wyrażenie zwróci false, jeśli zwróci false, wyrażenie zwróci true.




    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.019 sek.