Ποιο είναι το παράδειγμα της αδιανόητης γλώσσας;

Ένα από τα πιο διάσημα παραδείγματα μιας αδιανόητης γλώσσας είναι το πρόβλημα της στάσης .

Το πρόβλημα διακοπής:

Το πρόβλημα διακοπής είναι το πρόβλημα του προσδιορισμού, δεδομένης της περιγραφής ενός αυθαίρετου προγράμματος υπολογιστών και μιας εισόδου, είτε το πρόγραμμα θα τελειώσει ή θα συνεχίσει να τρέχει για πάντα. Πιο τυπικά, ρωτά:

* είσοδος: `` Πού:

* Το P` είναι μια μηχανή Turing (ή μια αναπαράσταση οποιουδήποτε προγράμματος υπολογιστών γενικής χρήσης).

* «Είμαι η είσοδος στο μηχάνημα Turing» P ».

* Έξοδος:

* "Ναι" αν το μηχάνημα Turing `p` σταματάει (τελειώνει την εκτέλεση) όταν δοθεί είσοδος` i '.

* "Όχι" αν το μηχάνημα Turing `P` δεν σταματάει (βρόχοι για πάντα) όταν δοθεί είσοδος` i '.

Γιατί είναι αδιαμφισβήτητο:

Το πρόβλημα διακοπής είναι αδιαμφισβήτητο, που σημαίνει ότι υπάρχει * όχι * μηχάνημα (ή αλγόριθμος) που μπορεί να λύσει σωστά το πρόβλημα διακοπής για * όλες τις πιθανές εισροές ``.

Η απόδειξη γίνεται συνήθως με αντίφαση. Ας υποθέσουμε ότι υπάρχει * μια μηχανή turing `h` που λύνει το πρόβλημα διακοπής. `H` παίρνει` `ως εισροές και εξόδους" ναι "αν` p` σταματάει στο `I 'και" όχι "αν` p` βρόχοι για πάντα στο `I'.

Στη συνέχεια, μπορούμε να κατασκευάσουμε ένα άλλο μηχάνημα Turing `d` (συχνά ονομάζεται" διαγώνια ") που χρησιμοποιεί το` h` ως υπορουτίνα:

`` `

Turing Machine D (P):

1. Εκτέλεση H (P, P) // Run H με το P τόσο ως πρόγραμμα όσο και η είσοδος

2. Εάν το h (p, p) επιστρέφει "ναι" (p σταματά στην είσοδο p):

Τότε βρόχο για πάντα.

3. Εάν το h (p, p) επιστρέφει "όχι" (p loops για πάντα στην είσοδο p):

Τότε σταματήστε.

`` `

Τώρα, τι συμβαίνει όταν τρέχουμε `d` με τον εαυτό του ως εισροή:` d (d) `;

* Σενάριο 1:Ας υποθέσουμε ότι «σταματάει»

- Αυτό σημαίνει ότι στο βήμα 1, `h (d, d)` επέστρεψε "ναι" (γιατί το `d` σταματάει αν και μόνο αν` h (d, d) λέει ότι 'd' σταματάει την είσοδο 'd').

- Αλλά αν το "H (D, D)" επέστρεψε "ναι", τότε το "D` σχεδιάστηκε για να βρόχο για πάντα (στο βήμα 2). Αυτό έρχεται σε αντίθεση με την παραδοχή μας ότι το «D (D)« σταματάει.

* Σενάριο 2:Ας υποθέσουμε ότι «D (d)` βρόχοι για πάντα.

- Αυτό σημαίνει ότι στο βήμα 1, `h (d, d) επέστρεψε" όχι "(επειδή` d` βρόχοι για πάντα αν και μόνο αν `h (d, d) λέει ότι` d` βρόχοι στην είσοδο 'd').

- Αλλά αν ο `h (d, d) επέστρεψε" όχι ", τότε το` d` σχεδιάστηκε για να σταματήσει (στο βήμα 3). Αυτό έρχεται σε αντίθεση με την παραδοχή μας ότι οι βρόχοι "D (D)" βρόχοι για πάντα.

Δεδομένου ότι και τα δύο σενάρια οδηγούν σε μια αντίφαση, η αρχική μας υπόθεση ότι υπάρχει μια μηχανή Turing `h` που λύνει το πρόβλημα διακοπής πρέπει να είναι ψευδής. Ως εκ τούτου, το πρόβλημα διακοπής είναι αδιαμφισβήτητο.

με απλούστερους όρους: Δεν μπορείτε να γράψετε ένα πρόγραμμα που μπορεί πάντα να προβλέψει αξιόπιστα εάν ένα άλλο πρόγραμμα θα σταματήσει ή θα τρέξει για πάντα.

Σημασία:

Η αδιαφορία του προβλήματος διακοπής έχει βαθιές επιπτώσεις στην επιστήμη των υπολογιστών. Δείχνει ότι υπάρχουν θεμελιώδη όρια σε ό, τι μπορούν να υπολογίσουν οι υπολογιστές. Χρησιμεύει επίσης ως βάση για την απόδειξη της μη αποικοδόμησης πολλών άλλων προβλημάτων. Εάν μπορείτε να δείξετε ότι η επίλυση ενός άλλου προβλήματος θα σας επιτρέψει να λύσετε το πρόβλημα διακοπής, τότε αυτό το άλλο πρόβλημα πρέπει επίσης να είναι ανεφάρμοστο.