Wersja z 04:53, 1 paź 2021 edytuj Janb1969 (dyskusja \| edycje) Redaktorzy 329 edycji lin. ← poprzednia edycja		Wersja z 05:44, 1 paź 2021 edytuj anuluj edycję Janb1969 (dyskusja \| edycje) Redaktorzy 329 edycji lin. następna edycja →
Linia 3: ==Entscheidungsproblem - tło historyczne== W 1928 [[David Hilbert]] przedstawił problem decyzyjny ([[Entscheidungsproblem]]) dotyczący teorii aksjomatycznych [[Logika pierwszego rzędu\|logiki pierwszego rzędu]], który można wyrazić następująco: podać algorytm rozstrzygający w skończonej liczbie kroków czy dla danego zbioru aksjomatów NT logiki pierwszego rzędu, zdanie T jest prawdziwe (czy T jest prawdziwe w każdym [[teoria modeli\|modelu]] spełniającym aksjomaty NT). Na mocy udowodnionego rok później [[~~Twierdzenie Gödla\|~~twierdzenia Gödla o zupełności]] tak postawiony problem jest równoważny pytaniu czy zdanie T może zostać dedukcyjnie wyprowadzone z aksjomatów NT (patrz: [[dedukcja naturalna]], [[system Hilberta]]). W 1931 [[Kurt Gödel]] pokazał, że system dowodzenia twierdzeń arytmetycznych sformalizowany w ramach [[Principia Mathematica]] nie jest zupełny i niesprzeczny. [[Twierdzenie Gödla\|Dowód Gödla]] jest czysto logiczny i nie odnosi się do żadnej notacji obliczalności, w związku z tym nie implikuje bezpośrednio nierozstrzygalności w obrębie zdań systemów aksjomatycznych logiki pierwszego rzędu.

Dowód Turinga: Różnice pomiędzy wersjami