Dowód Turinga – dowód przedstawiony przez Alana Turinga w 1937 w pracy "On Computable Numbers, With an Application to the Entscheidungsproblem" pokazujący, że pewne ogólne klasy problemów są nierozstrzygalne, to znaczy nie istnieje uniwersalny algorytm rozwiązujący każdą instancje problemów z tych klas. W szczególności dowód daje negatywną odpowiedź na Entscheidungsproblem.
Entscheidungsproblem - tło historyczne
W 1928 David Hilbert przedstawił problem decyzyjny (Entscheidungsproblem) dotyczący teorii aksjomatycznych 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 modelu spełniającym aksjomaty NT). Na mocy udowodnionego rok później 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).