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

Usunięte 19 bajtów ,  7 miesięcy temu
lin.
(lin.)
(lin.)
 
==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.