Perché il problema di fermezza è decidabile per GOTO LANGUES LIMITED sul valore più alto di costanti e variabili?

Question

Questo è preso da un vecchio esame della mia università che sto usando per prepararmi per l'esame in arrivo:

Dato è una lingua $ \ text {goto} _ {17} ^ c \ SometeTQ \ testo {goto} $ . Questa lingua contiene esattamente quelle $ \ testo {goto} $ programmi in cui nessuna costante è mai superiore a $ 17 $ né qualsiasi variabile mai superiore a $ c $ .

$ goto $ qui descrive l'insieme di tutti i programmi scritti nella $ goto $ in lingua dei seguenti elementi:

con variabili $ v_i \ in \ mathbbs {n} $ e costanti $ c \ in \ mathbb {n} $
Assegnazione: $ x_i:= c, x_i:= x_i \ pm c $
Salto condizionale: se (confronto) goto $ l_i $
HALTCOMMAND: HALT

Attualmente sto lottando con la formalizzazione di una prova, ma questo è quello che sono arrivato finora, formulato molto casualmente: Per qualsiasi programmato programma in questo set sappiamo che è finito. Un programma finito contiene una quantità finita di variabili e una quantità finita di stati o linee da entrare. Come tale, vi è una quantità finita di configurazioni in cui questo processo può essere. Se lasciamo funzionare questo programma, possiamo mantenere un elenco di tutte le configurazioni che abbiamo visto. Cioè, la combinazione di tutti i valori variabili usati e lo stato del programma. Se lasciamo funzionare il programma, ci deve essere una delle due cose che succede alla fine: Il programma si ferma. In questo caso, restituiamo Sì e abbiamo deciso che si ferma. Il programma raggiunge una configurazione che è stata registrata prima. Poiché la lingua è deterministica, ciò significa che dobbiamo essere andati un loop completo che ripeterà esattamente ora.

Nessun altro caso può esistere come ciò significherebbe che continuiamo a correre per sempre sul codice finito senza ripetere una configurazione. Questo significa dopo ogni passo, tra il nostro elenco di passaggi infiniti, c'è una nuova configurazione. Ciò significherebbe che ci sono configurazioni infinite, che è una contraddizione.

è corretto? Inoltre, come sarebbe una prova di prova più formale se è? In caso contrario, come sarebbe un aspetto corretto della prova?

Answer 1

Esiste un numero finito di stati diversi (il set di valori delle variabili e il contatore del programma).I tuoi "programmi di goto limitato" sono solo un modo (disordinato) per descrivere un automa deterministico finito.

O solo per la ragione che il programma afferma di essere finito, è certamente possibile mappare tutti i possibili calcoli non looping (da qualcosa come una prima ricerca della ricerca del grafico degli stati e dei vicini).