Nota storica: nel suo famoso articolo del 1937, On computable numbers, with an application to the Entscheidungsproblem, Alan Turing dimostrò che il problema della fermata non è decidibile: tra le conseguenze, quindi, il fatto che non è possibile scrivere un programma che decida se una macchina di Turing si arresti, dato un particolare input.
Turing però è convinto che il problema della fermata sia decidibile nel modello di seguito descritto, dove si utilizza una macchina di Turing di sola lettura.
La macchina ha un nastro di N celle, numerate da 0 a N-1, da sinistra verso destra.
In ogni cella c’è un numero intero, e le celle sono di sola lettura: la macchina non può cambiare il contenuto della cella.
La macchina di Turing ha una tabella di transizione, che in funzione dello stato attuale e del numero letto, cambia lo stato interno della macchina e comanda alla macchina di spostarsi di un certo numero di celle, verso destra o verso sinistra.
La cella numero 0 è una cella speciale: quando la macchina di Turing arriva nella cella 0, termina la sua computazione e si ferma.
Considerate la figura: qui vedete il nastro, con 5 celle numerate da 0 a 4, contenenti interi compresi tra 0 e 2, e la tabella di transizione, che in funzione dei due stati possibili della macchina (a e b) e dei tre interi letti dalla cella, riporta lo stato successivo e lo spostamento della macchina, rappresentato da interi positivi per spostamenti verso destra e interi negativi per spostamenti verso sinistra.
Per esempio, supponiamo che la macchina di Turing sia inizialmente nello stato a e che parta dalla cella 1.
Nella cella 1 la macchina legge l’intero 2: come si vede dalla tabella, la macchina di Turing rimane nello stato a e si sposta di una cella a destra.
Finisce quindi nella cella 2, dove legge l’intero 1: a questo punto rimane nello stato a e si sposta di due celle a sinistra; raggiunge quindi la cella 0 e si ferma.
Se la macchina di Turing parte, sempre nello stato a, dalla cella 2 vediamo che termina direttamente nella cella 0, fermandosi.
Viceversa, se la macchina di Turing, sempre nello stato a, parte dalla cella 3 si vede che la macchina cambia stato, passando allo stato b e spostandosi di due celle all’indietro.
Si ritrova quindi nella cella 1 ma qui, dalla tabella di transizione, si vede che ritorna nello stato a e si risposta di due celle in avanti, ritornando nella cella 3.
Da qui continuerà a spostarsi, alternativamente, di due celle in avanti e due celle indietro, cambiando stato a ogni spostamento.
Quindi, la macchina di Turing a partire da questa configurazione iniziale, NON termina.
Il vostro compito è quello di aiutare Alan Turing, scrivendo un programma che, presa in ingresso la descrizione di una macchina di Turing, lo stato iniziale della macchina e la configurazione del nastro, stampi tutti e soli i numeri delle celle tali che, se la computazione parte da quella cella, la macchina di Turing si arresta.
Ad esempio, con riferimento alla figura, le celle per cui la macchina di Turing termina, partendo dallo stato iniziale a sono la 0 (che per definizione appartiene alla soluzione), la 1, la 2 e la 4.
Partendo dallo stato iniziale b le celle in cui la macchina di Turing termina sono la 0, la 2 e la 3.
Ottiene il 64% del punteggio con le istanze di dimensione ragionevoli…
/* www.valcon.it OII 2012 - Fase nazionale - Entscheidungsproblem, o problema della fermata */ #include#include #define MAXSC 10000000 #define MAXSN 1000000 #define MAXN 1000000 #define TERMINA 1 #define NON_TERMINA 2 #define AVVENUTO 1 #define NON_AVVENUTO 0 using namespace std; int NUOVO_STATO[MAXSC]; // transizione di stato int SPOSTAMENTO[MAXSC]; // e spostamento int CELLE [MAXN ]; // contenuto int CELLE_INFO [MAXN ]; // termina o non termina? int EVENTO_INFO[MAXSN]; // stato-cella già avvenuto? int main() { ifstream fin ( "input.txt"); ofstream fout("output.txt"); int N, // lunghezza del nastro S, // n. di stati C; // n. di caratteri distinti nelle celle int stato_corrente, // le quartuple... carattere_letto, nuovo_stato, spostamento; //------------------------------------------------------------------------ fin >> N >> S >> C; for(int i=0; i < S; i++) for(int j=0; j < C; j++) { fin >> stato_corrente >> carattere_letto >> nuovo_stato >> spostamento; NUOVO_STATO[C*stato_corrente+carattere_letto]=nuovo_stato; SPOSTAMENTO[C*stato_corrente+carattere_letto]=spostamento; } for(int i=0; i < N; i++) fin >> CELLE[i]; //------------------------------------------------------------------------ int cella_iniziale, evento, stato, cella_corrente; bool ancora; CELLE_INFO[0]=TERMINA; for(cella_iniziale=1; cella_iniziale < N; cella_iniziale++) { for(int i=0; i < S*N; i++) EVENTO_INFO[i]=NON_AVVENUTO; stato_corrente=0; cella_corrente=cella_iniziale; do { ancora =false; evento =N*stato_corrente+cella_corrente; carattere_letto=CELLE[cella_corrente]; stato =C*stato_corrente+carattere_letto; if(EVENTO_INFO[evento] == AVVENUTO) CELLE_INFO[cella_iniziale]=NON_TERMINA; else { stato_corrente =NUOVO_STATO[stato]; cella_corrente+=SPOSTAMENTO[stato]; if(cella_corrente == 0) CELLE_INFO[cella_iniziale]=TERMINA; else { EVENTO_INFO[evento]=AVVENUTO; ancora=true; } } } while(ancora); } //------------------------------------------------------------------------ int contatore=0; for(cella_iniziale=0; cella_iniziale < N; cella_iniziale++) if(CELLE_INFO[cella_iniziale] == TERMINA) contatore++; fout << contatore << endl; for(cella_iniziale=0; cella_iniziale < N; cella_iniziale++) if(CELLE_INFO[cella_iniziale] == TERMINA) fout << cella_iniziale << endl; return 0; }