Logica e flusso del programma che trasmettono stato e tempo?

Question

Mi chiedo se sarebbe mai utile indicizzare ogni possibile stato di un'applicazione usando alcune chiavi di riferimento ...

Significato, diciamo che abbiamo un programma che inizia, ha solo così tanti esiti possibili, diciamo 8.

ma se ogni risultato è raggiunto attraverso il passaggio attraverso molti più stati logici, e tra ogni ramo è considerato uno stato ed è mappato su una chiave.

Potrebbe richiedere molta memoria in programmi di grandi dimensioni, ma se potessimo accedere direttamente a una chiave (la chiave potrebbe essere basata sul tempo o sulla profondità della logica), potremmo attraversare istantaneamente tutte le possibili situazioni senza dover iniziare l'intero processo di nuovo con nuovi dati.

Pensalo come un albero in cui i nodi senza figli sono i risultati finali e ogni ramo tra un nodo e i suoi genitori o figli è uno 'stato', ognuno con una chiave diversa. Quindi, mentre ci sono solo 8 foglie, o risultati finali del processo, potrebbero esserci molti "stati" a seconda della profondità della logica che scende dall'albero prima di rimanere senza figli.

Forse per le simulazioni, ma ci vorrebbe un sacco di memoria.

Answer 1

Ryan, la risposta è definitivamente SÌ.

Contrariamente alla prima risposta, il problema dell'arresto non dimostra nulla. In effetti, Ryan, ciò che stai suggerendo dimostra che l'arresto del problema wrong non si applica ai veri computer digitali, e ho già usato questo esempio come prova prima.

In un sistema digitale deterministico (ovvero un programma in esecuzione su hardware digitale reale), il numero di stati possibili è finito, e quindi tutti gli stati possibili sono enumerabili.

La quantità esatta di memoria richiesta per l'hash sarebbe:

(2) * (dimensione dello stato del programma) * (numero di stati iniziali)

Lo stato iniziale sarebbe la tua chiave hash, e lo stato finale sarebbe il valore hash, e quindi avresti una coppia chiave / valore per ogni stato iniziale.

Per un sistema operativo, la dimensione dello stato del programma "quot" è 2 ^ (gigabit totali di memoria su tutti i dispositivi di sistema). Ovviamente, un programma così ampio e di uso generale richiederebbe una quantità impraticabile di memoria per l'hash, e non sarebbe comunque utile, poiché il sistema è autoreferenziale / irriducibilmente complesso (ovvero l'input dell'utente successivo dipende dall'output del sistema precedente).

Spiegazione:

Questo è molto utile, perché se indicizzi ogni possibile stato iniziale e lo associ allo stato finale, porteresti a zero il tempo di esecuzione di QUALSIASI PROGRAMMA! Per zero intendo un tempo di esecuzione O (1) molto veloce - il tempo necessario per cercare lo stato finale (se termina).

L'esecuzione di un programma, a partire da ciascuno di tutti gli stati possibili, fornirà una sorta di mappa degli stati che mostra i cicli. Il problema dell'arresto è quindi risolto, perché ci sono solo tre (in realtà quattro che crollano a tre) possibilità date ogni possibile stato iniziale:

1. Il programma rientrerà in uno stato precedentemente rilevato (dallo stato iniziale), prima di esaurire tutti gli stati possibili, e quindi ricorre logicamente per sempre.
2. Il programma raggiunge uno stato identificato come "terminazione" prima che abbia la possibilità di rientrare in uno stato precedentemente incontrato o esaurire tutti gli stati possibili (dallo stato iniziale).

3. o 4. Il programma più semplice si avvierà da uno stato iniziale, entrerà in tutti gli stati possibili esattamente una volta e quindi non avrà altra scelta che (3) arrestare o (4) rientrare in uno stato precedentemente incontrato e scorrere per sempre .

   per (int i = 0; true; i ++); // raggiungerò il valore massimo, passerò nuovamente a zero, a quel punto sarà rientrato nello stato iniziale

Quindi, in sostanza, il tuo indice potrebbe essere descritto in questo modo:

• Per ogni stato iniziale, esistono esattamente uno o zero stati di chiusura.

In altre parole, per ogni stato iniziale, il programma raggiunge uno stato finale o rientra in uno stato già incontrato dallo stato iniziale e scorre all'infinito.

Quindi, per qualsiasi programma in esecuzione su hardware digitale deterministico , è assolutamente possibile (ma spesso non pratico ) per determinare tutti i suoi stati e se si ferma o si avvolge per sempre.

• La praticità dipende esclusivamente da quanti stati iniziali validi hai (che puoi ridurre drasticamente con vincoli di input) e da quanto sia fattibile impiegare il tempo per eseguire il programma per ognuno di essi per terminare e memorizzare lo stato risultante nella tabella hash.

Oltre a forzare il tempo di esecuzione di qualsiasi programma un'operazione O (1), altri usi dello stato di acquisizione includono la funzione di salvataggio dello stato negli emulatori della console di gioco e la funzione di ibernazione dei computer (sebbene non sia un perfetto ripristino dello stato, poiché alcune memorie di sistema deve essere utilizzato per il codice che ripristina lo stato e parte della memoria potrebbe non essere mai memorizzata (ad es. memoria GPU)).

Ciò che dimostra è che qualsiasi programma può essere rappresentato da una tabella hash. Qualsiasi programma può essere rappresentato da una mappa di transizione di stato iniziale-finale. Tutti i programmi possono essere semplificati in un'unica grande funzione con un ingombro di memoria enorme!

Answer 2

Questo non sarebbe possibile risolvere per un programma generale. Il problema di arresto dimostra che è impossibile determinare se un programma si arresterà. Il problema di determinare se un determinato stato è possibile è riducibile al problema dell'arresto, quindi nemmeno risolvibile.

Answer 3

Penso che questo approccio sarebbe totalmente intrattabile per qualsiasi cosa.

Come problema di ricerca, è troppo grande. Se assumiamo che ogni stato possa portare a 10 risultati (anche se penso che questo numero sia davvero basso), quindi per guardare a soli 20 passi avanti, ora dobbiamo tenere traccia di 200 miliardi di possibilità.

E ricorda che ogni passaggio in un ciclo conta come punto di diramazione. Quindi, se abbiamo un codice simile al seguente:

for (int i=0; i < 100; i++)
    some_function();

Quindi il numero di stati possibili è (numero di rami all'interno di some_function) ^ 100

Answer 4

Sebbene Josh abbia ragione nel dire che non puoi rispondere alla versione più liberale di questo problema a causa dell'ambiguità di esso, puoi rispondere se poni alcune limitazioni sul tuo scenario. C'è una grande differenza tra lo stato del tuo programma e lo stato delle entità commerciali.

Ad esempio, supponiamo di avere un'applicazione orientata al flusso di lavoro definita da un DFA (State Machine). In realtà potresti quindi associare un determinato punto in quel DFA con un ID di qualche tipo.

Quindi sì, è trattabile ma non senza restrizioni.

Answer 5

Questo viene fatto a livello di funzione; è una tecnica chiamata memoization .

Answer 6

Ricerca strutture kripke e logica modale. Questo è un approccio adottato nei programmi di modellizzazione. Dimentico quali sono i sistemi classici che utilizzano questo approccio.