Mașină Gödel-incompletă
Prin mașină incompletă Gödel înțelegem o mașină care poate funcționa cât consideră necesar, care poate emite pe propria bandă extensibilă nelimitat (pe scurt: poate imprima) șiruri care pot fi interpretate ca afirmații despre propriul comportament, știind cum pentru a distinge afirmații adevărate în cadrul acestora.
Să dăm un exemplu propus de Raymond Smullyan .
Numim M o mașină de genul mașinii Turing capabilă să tipărească pe panglici nelimitate șiruri pe alfabetul a cinci simboluri A = {~, P , E , (,)}. Cerem ca M să aibă capacitatea de a parcurge toate șirurile de pe A (de exemplu, în funcție de ordinea ascendentă-lexicografică a lungimii).
Spunem extinderea unui șir W peste A șirul peste A de forma W ( W ). De interes particular sunt siruri de caractere pe care o vom spune judecăți de sine și o interpretare a acestora care le consideră declarații cu privire la comportamentul M însăși, așa cum este indicat în imaginea de mai jos:
- P ( W ) șirul W este imprimabil ;
- PE ( W ) extensia șirului W este imprimabilă ;
- ~ P ( W ) șirul W nu se poate imprima ;
- ~ PE ( W ) extensia șirului W nu este imprimabilă .
Auto-rapoartelor li se poate acorda o evaluare booleană după cum urmează:
- P ( W ) este adevărat dacă W este tipărit, este fals în caz contrar;
- PE ( W ) este adevărat dacă W ( W ) este imprimabil, altfel este fals;
- ~ P ( W ) este adevărat dacă W nu este tipărit, altfel este fals;
- ~ PE ( W ) este adevărat dacă W ( W ) nu este imprimabil, altfel este fals.
De asemenea, lui M i se cere să posede dispozitive care îi permit să distingă adevăratele auto-judecăți de cele false. Această cerere este legitimată de faptul că M este capabil să procedeze la imprimarea tuturor șirurilor de imprimare, adică de faptul că problema caracterului de imprimare sau nu a șirurilor de pe A este decisă. Prin urmare, mașinii M i se poate cere să imprime, pe lângă șirurile care nu pot fi auto-propuse, toate autofrazele adevărate și nu cele false.
Să examinăm acum judecata de sine G : = "~ PE (~ PE )".
G este adevărat dacă și numai dacă extensia „~ PE ” nu este imprimabilă. Dar această extensie este G în sine, deci G este adevărat dacă și numai dacă nu este imprimabilă. Prin urmare, aut G este adevărat și nu poate fi imprimat, aut este imprimabil și fals. Cea de-a doua alternativă încalcă însă neprimabilitatea falselor auto-propoziții. În concluzie, G trebuie să fie adevărat, dar nu poate fi tipărit.
De asemenea, se observă că auto-propoziția „ PE (~ PE )”, negarea celei anterioare, trebuie să fie falsă și nu poate fi tipărită nici ea. Este un exemplu de șir indecidabil pentru M , deoarece nici el, nici negarea acestuia nu pot fi tipărite.
Mașina introdusă poate fi considerată un caz deosebit de simplu al unui sistem formal dotat cu o anumită abilitate de a reflecta asupra propriului comportament și capabil să demonstreze anumite propoziții formulate folosind cele 5 simboluri ale alfabetului A. Acum litera P trebuie interpretată cu atributul „demonstrabil”, iar șirul „~ PE (~ PE )” constituie o adevărată auto-judecată care în sistemul formal nu poate fi dovedită.
Mașina introdusă oferă astfel un indiciu pentru înțelegerea teoremei incompletitudinii lui Gödel .
Mai mult, poate fi considerat un exemplu de limitare a conștiinței de sine a unui sistem.
Bibliografie
- ( EN ) Raymond M. Smullyan , The Gödel's Incompleteness Theorems , Oxford University Press , 1992, ISBN 0-19-504672-2 . Adus la 11 noiembrie 2012 .
