La rilevazione di loop infinito in brainfuck programma

StackOverflow https://stackoverflow.com/questions/367571

Domanda

Ho scritto un semplice brainfuck interprete MATLAB script language.Essa è alimentata casuale bf programmi da eseguire (come parte di un algoritmo genetico progetto).Il problema che ho è la faccia, il programma risulta avere un ciclo infinito in un numero considerevole di casi, e quindi il GA si blocca al punto.
Così, ho bisogno di un meccanismo per rilevare un loop infinito e di evitare l'esecuzione di codice in bf.
Ovvio che (banale) caso è da quando ho

[]

Posso rilevare questo e si rifiuta di eseguire il programma.
Per il non banale casi, ho capito che l'idea di base è:per determinare come una iterazione del ciclo cambia la cella corrente.Se il cambiamento è negativo, si sta finalmente andando a raggiungere lo 0, quindi è un ciclo limitato.Altrimenti, se il cambiamento non è negativo, è un ciclo infinito.
L'attuazione di questo è facile per il caso di un singolo loop, ma con cicli nidificati diventa molto complicato.Per esempio, (in quanto segue (1) si riferisce al contenuto della cella 1, etc.)

++++ Put 4 in 1st cell (1)
>+++ Put 3 in (2)
<[   While( (1) is non zero)
    --   Decrease (1) by 2
    >[   While( (2) is non zero)
        -    Decrement (2)
        <+   Increment (1) 
    >]   
    (2) would be 0 at this point
    +++  Increase (2) by 3 making (2) = 3
<]   (1) was decreased by 2 and then increased by 3, so net effect is increment

e, di conseguenza, il codice viene eseguito su e su.Un ingenuo controllo del numero di +'s e's fatto sul cell 1, tuttavia, direi che il numero di's è di più, in modo da non rilevare che il ciclo infinito.
Qualcuno può pensare a un buon algoritmo per rilevare un loop infinito, arbitraria di nidificazione di un arbitrario numero di cicli in bf?

EDIT:So che il problema della terminazione non è risolvibile in generale, ma non ero sicuro se non esisteva caso speciale eccezioni.Come, forse Matlab potrebbe funzionare come una Super macchina di Turing in grado di determinare l'arresto del bf programma.Potrei essere terribilmente male, ma se è così, vorrei sapere esattamente come e perché.

LA SECONDA MODIFICA:Ho scritto quello che ho la pretesa di essere infinite loop detector.Probabilmente manca alcuni casi limite (o meno probabilmente, in qualche modo sfugge il SignorTuring frizioni), ma sembra funzionare per me ora come ora.In pseudocodice forma, qui va:

subroutine bfexec(bfprogram)
begin
    Looping through the bfprogram,
        If(current character is '[')
            Find the corresponding ']'
            Store the code between the two brackets in, say, 'subprog'
            Save the value of the current cell in oldval
            Call bfexec recursively with subprog
            Save the value of the current cell in newval
            If(newval >= oldval)
                Raise an 'infinite loop' error and exit
            EndIf
        /* Do other character's processings */
        EndIf
    EndLoop
end
È stato utile?

Soluzione

Quando ho usato programmazione genetica lineare, ho solo usato un limite superiore per il numero di istruzioni di un singolo programma è stato permesso di fare nella sua vita. Credo che questo è ragionevole in due modi: Non posso davvero risolvere il problema della terminazione in ogni caso, e programmi che richiedono troppo tempo per calcolare non sono degni di ottenere più tempo in ogni caso

.

Altri suggerimenti

Alan Turing vorrebbe avere una parola con voi.

http://en.wikipedia.org/wiki/Halting_problem

Diciamo che hai scritto un programma che potrebbe rilevare se questo programma verrebbe eseguito in un ciclo infinito. Diciamo che per ragioni di semplicità che questo programma è stato scritto in brainfuck per analizzare i programmi Brainfuck (anche se questo non è un presupposto delle seguenti prove, perché qualsiasi lingua in grado di emulare brainfuck e brainfuck può emulare qualsiasi lingua).

Ora diciamo che si estende il programma di controllo per fare un nuovo programma. Questo nuovo programma esce immediatamente quando il suo ingresso loop a tempo indeterminato, e loop per sempre quando il suo ingresso esce a un certo punto.

Se si immette questo nuovo programma in sé, quali saranno i risultati essere?

Se questo programma loop per sempre quando viene eseguito, quindi per sua stessa definizione, che dovrebbe uscire immediatamente quando viene eseguito con se stesso come input. E viceversa. Il programma di controllo non può esistere, perché la sua stessa esistenza implica una contraddizione.

Come è stato accennato in precedenza, si sono essenzialmente ribadendo il famoso problema della terminazione: http://en.wikipedia.org/wiki/Halting_problem

Ed. Voglio mettere in chiaro che quanto sopra confutazione non è mia, ma è essenzialmente la famosa confutazione Alan Turing ha dato indietro nel 1936.

Stato bf è una singola matrice di caratteri.

Se fossi in te, mi piacerebbe prendere un hash dello stato bf interprete in ogni "]" (o una volta in rand (1, 100) "]" s *) e affermare che l'insieme di hash è unico.

Il secondo (o più) volta che vedo un certo hash, risparmio il tutto lo stato da parte.

Il terzo (o più) volta che vedo un certo hash, ho confrontare l'intero stato ai salvati uno (s) e se c'è una corrispondenza, ho smesso.

In ogni comando di input ( '', IIRC) a reimpostare i miei stati e la lista di hash. Salvati

L'ottimizzazione è quello di hash solo la parte dello stato che è stato toccato.

Non ho risolto il problema della terminazione - Sto rilevando un loop infinito durante l'esecuzione il programma

.

* La Rand è quello di rendere indipendente di controllo del periodo di ciclo

ciclo infinito non può essere rilevato, ma è in grado di rilevare se il programma sta prendendo troppo tempo.

Implementare un timeout incrementando un contatore ogni volta che si esegue un comando (per esempio <, >, +, -). Quando il contatore raggiunge un certo numero, che si imposta con l'osservazione, si può dire che ci vuole molto tempo per eseguire il programma. Per il vostro scopo, "molto lungo" e infinito è una buona-sufficiente approssimazione.

Come già detto questo è il Problema della terminazione.Ma nel tuo caso ci potrebbe essere una soluzione:Il Problema della terminazione è considerando che è circa la macchina di Turing, che ha un numero illimitato di memoria.

Nel caso In cui sai che hai un limite di memoria (ad es.sai che non lo uso più di 10 celle di memoria), è possibile eseguire il programma e stop.L'idea è che il calcolo dello spazio di limiti di tempo di calcolo (come si può scrivere più di una cella a un passo).Dopo aver eseguito quanto più passaggi si possono avere diverse configurazioni di memoria, si può rompere.E. g.se si dispone di 3 celle, con 256 condizioni, si può avere un massimo di 3^256 diversi stati, e così si può interrompere dopo l'esecuzione che molti passaggi.Ma attenzione, ci sono implicite le cellule, come il puntatore all'istruzione e registri.Si fa ancora di più, se si salva ogni configurazione dello stato e non appena si rileva, che hai già avuto, hai un infite loop.Questo approccio è sicuramente molto meglio in fase di esecuzione, ma loro esigenze molto più spazio (qui potrebbe essere adatto per l'hash le configurazioni).

Questo non è il problema della terminazione, tuttavia, non è ancora ragionevole tentare di rilevare arrestare anche in una macchina così limitato come una macchina BF 1000 cella.

Consideriamo questo programma: 

+[->[>]+<[-<]+]

Questo programma non si ripeterà fino a quando non ha riempito l'intero di memoria che per appena 1000 cellule richiederà circa 10 ^ 300 anni.

Al largo della parte superiore della mia testa (e potrei sbagliarmi), penserei che sarebbe stato un po 'difficile da individuare se un programma ha un loop infinito senza in realtà l'esecuzione del programma stesso.

Come esecuzione condizionale di porzioni del programma dipende lo stato di esecuzione del programma, sarà difficile conoscere lo stato particolare del programma senza eseguire effettivamente il programma.

Se non si richiede che un programma con un ciclo infinito essere eseguito, si potrebbe provare con un contatore di "istruzioni eseguite", e solo eseguire un numero finito di istruzioni. In questo modo, se un programma ha un ciclo infinito, l'interprete può terminare il programma che viene bloccato in un ciclo infinito.

Se non ricordo male, il problema della terminazione prova era vero solo per qualche caso estremo che ha coinvolto di riferimento di sé. Tuttavia è ancora banale per mostrare un esempio pratico del motivo per cui non si può fare un rilevatore di ciclo infinito.

ultimo teorema di Fermat . E 'facile creare un programma che consente di scorrere ogni numero (o in questo caso 3 numeri), e rileva se si tratta di un controesempio al teorema. Se così è ferma, altrimenti si continua.

Quindi, se si dispone di un rilevatore di ciclo infinito, dovrebbe essere in grado di dimostrare questo teorema, e molti molti altri (forse tutti gli altri, se possono essere ridotti alla ricerca di controesempi.)

In generale, qualsiasi programma che coinvolge scorrendo numeri e fermandosi solo sotto qualche condizione, richiederebbe una cella generale teorema di dimostrare se tale condizione può mai essere soddisfatta. E questo è il caso più semplice di loop che ci sia.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top