Arresto in lingue non complete di Turing

Question

Il problema di arresto non può essere risolto per i linguaggi completi di Turing e può essere risolto banalmente per alcuni linguaggi non TC come regex dove si ferma sempre.

Mi chiedevo se ci fossero delle lingue che hanno sia la capacità di fermarsi che di non fermarsi, ma ammette un algoritmo in grado di determinare se si ferma.

Answer 1

Sì. Una classe importante di questo tipo sono le funzioni ricorsive primitive . Questa classe include tutte le cose di base che ti aspetti di poter fare con i numeri (addizione, moltiplicazione, ecc.), Così come alcune classi complesse come @adrian ha menzionato (espressioni regolari / automi finiti, grammatiche / pushdown senza contesto automi). Esistono tuttavia funzioni che non sono ricorsive primitive, come la funzione di Ackermann .

In realtà è abbastanza facile capire le funzioni ricorsive primitive. Sono le funzioni che potresti ottenere in un linguaggio di programmazione che non ha avuto una vera ricorsione (quindi una funzione f non può chiamare se stessa, direttamente o chiamando un'altra funzione g che quindi chiama f, ecc.) E non ha cicli di tempo, invece avendo limitato i for-loop. Un ciclo for limitato è uno come "quot" per i da 1 a r " dove r è una variabile che è già stata calcolata in precedenza nel programma; inoltre, non posso essere modificato all'interno del for-loop. Il punto di tale linguaggio di programmazione è che ogni programma si ferma.

La maggior parte dei programmi che scriviamo sono in realtà ricorsivi primitivi (voglio dire, possono essere tradotti in un tale linguaggio).

Answer 2

Il problema di arresto non agisce sulle lingue. Piuttosto, agisce sulle macchine (ad esempio, programmi): chiede se un determinato programma si arresta su un determinato input.

Forse intendevi chiedere se può essere risolto per altri modelli di calcolo (come le espressioni regolari, di cui parli, ma che ti piace anche automi push-down ).

In generale, l'arresto può essere rilevato in modelli con risorse limitate (come espressioni regolari o, equivalentemente, automi finiti, che hanno un valore fisso numero di stati e nessuna memoria esterna). Questo è facilmente realizzabile da elencando tutte le possibili configurazioni e controllando se la macchina entra la stessa configurazione due volte (indicando un loop infinito); con finito risorse, possiamo mettere un limite superiore alla quantità di tempo prima che dobbiamo vedere una configurazione ripetuta se la macchina non si ferma.

Di solito, modelli con risorse infinite (TM e PDA illimitati, per esempio), non può essere arrestato, ma sarebbe meglio investigare i modelli e i loro problemi aperti individualmente.

(Siamo spiacenti per tutti i link di Wikipedia, ma in realtà è un'ottima risorsa per questo tipo di domanda.)

Answer 3

La risposta breve è sì e tali lingue possono anche essere estremamente utili.

Qualche mese fa è stato discusso su LtU: http://lambda-the-ultimate.org/node/2846