Estado e lógica transcendendo tempo e fluxo de programa?

Question

Quer saber se ele nunca iria ser útil para indexar todos os estados possíveis de um aplicativo usando algumas chaves de referência ...

Ou seja, dizer que temos um programa que começa, tem apenas tantos resultados possíveis, digamos, 8.

mas se cada resultado é alcançado através percorrendo muitos estados mais lógica, e entre cada ramo é considerado um estado e é mapeado para uma chave.

Ele poderia ter um monte de memória em grandes programas, mas se pudéssemos acessar uma chave diretamente (a chave poderia ser baseado no tempo ou profundidade de lógica), então poderíamos instantaneamente atravessar qualquer uma das possíveis situações sem ter que começar todo o processo de novo com novos dados.

Pense nisso como uma árvore onde os nós sem filhos são resultados finais, e todos os ramos entre um nó e é pais ou filhos é um 'estado', cada uma com chave diferente. Assim, enquanto há apenas 8 folhas, ou resultados finais do processo, pode haver muitos estados "dependendo de quão profundo a lógica vai para baixo da árvore antes de ficar sem filhos.

Talvez para simulações, mas que seria necessário uma tonelada de memória.

Answer 1

Ryan, a resposta é definitivamente SIM.

Ao contrário da primeira resposta, o problema da parada não prova nada. Na verdade, Ryan, o que você está sugerindo comprova o problema da parada errado não se aplica a computadores digitais reais, e eu usei este mesmo exemplo, como uma prova de que antes.

Em um sistema digital determinística (ou seja, um programa rodando em hardware digital real), o número de estados possíveis é finito e, portanto, todos os estados possíveis são enumeráveis.

A quantidade exata de memória necessária para o hash seria:

(2)*(program state size)*(number of initial states)

O estado inicial seria a chave hash e estado final seria o valor de hash, e então você teria um par chave / valor para cada estado inicial.

Para um sistema operacional, o "tamanho estado de programa" é de 2 ^ (gigabits total de memória em todos os dispositivos do sistema). Obviamente, uma tal grande programa finalidade, geral exigiria uma quantidade impraticável de memória para mistura, e não seria de qualquer maneira útil, uma vez que o sistema é auto-referenciar / irredutível complexo (ou seja, ao lado de entrada de utilizador depende da saída do sistema anterior).

Explicação:

Isto é muito útil, porque se você índice de cada estado inicial possível e associá-lo com o estado de terminação, você seria efetivamente trazer o tempo de execução de qualquer programa para zero! Qualquer por zero quero dizer um ó muito rápido (1) tempo de execução -. O tempo que leva para procurar o estado de terminação (se ele termina)

A execução de um programa, a partir de cada um de todos os estados possíveis, irá fornecer uma espécie de estado mapa mostrando ciclos. O problema da parada é portanto resolvido, porque existem apenas três (quatro, na verdade, em colapso para três possibilidades) dada qualquer possível estado inicial:

1. O programa irá reentrar um estado encontradas anteriormente (desde que o estado inicial), antes de esgotar todos os estados possíveis, e, portanto, logicamente laços para sempre.
2. O programa atinge um estado identificado como "terminar" antes que ele tenha a chance de entrar novamente um estado previamente encontrado ou esgotar todos os estados possíveis (uma vez que o estado inicial).

3. ou 4. O programa mais simples vai começar a partir de um estado inicial, entrará todos os estados possíveis exatamente uma vez, e depois não tem escolha a não ser (3) suspensão ou (4) reenter um estado previamente encontrado e em laço para sempre .

   for (int i = 0; verdadeiro; i ++); // i chegará max-valor, rolar de volta para zero, altura em que terá reentrou o estado inicial

Então, basicamente, o seu índice poderia ser descrito assim:

• Para cada estado inicial, há exatamente um ou zero estados de terminação.

Em outras palavras, para cada estado inicial, o programa tanto atinge um estado de terminação ou reentra um estado já encontrou uma vez que o estado inicial e ciclos indefinidamente.

Assim, para qualquer programa em execução no hardware digital determinista , é absolutamente possível (mas muitas vezes Não é prático ) para determinar todos os seus estados e se ele pára ou laços para sempre.

• A praticidade depende unicamente de quantos estados iniciais válidos que você tem (que você pode reduzir drasticamente com restrições de entrada), e como viável é tomar o tempo para executar o programa para cada um deles à rescisão e armazenar o estado resultante na tabela de hash.

Além de impor tempo de execução de qualquer programa de O (1) operação, outras utilizações de captura de estado incluem a função de economia de estado na consola emuladores de jogos e o recurso de hibernação de computadores (embora não seja uma restauração perfeita de Estado, uma vez que alguns memória do sistema deve ser utilizado para o código que restaura o estado e alguns memória nunca podem ser armazenados (por exemplo GPU memória)).

O que isto prova é que qualquer programa pode ser representado por uma tabela hash. qualquer programapode ser representado por um mapa inicial-a-finais de transição de estado. Todos os programas podem ser simplificada para uma função grande com uma enorme memória de pegada!

Answer 2

Isto não seria possível resolver para um programa geral. O problema da parada prova que é impossível determinar se um programa vai parar. O problema de determinar se um determinado estado é possível é redutível ao problema da parada, portanto, não pode ser resolvido também.

Answer 3

Penso que esta abordagem seria totalmente intratável para, bem, nada.

Como um problema de pesquisa, é muito grande. Se assumirmos que cada estado pode levar a 10 resultados (embora eu acho que esse número é realmente baixo), depois de olhar apenas 20 passos à frente, agora temos de manter o controle de 200 bilhões de possibilidades.

E lembre-se que cada passo em uma contagem de loop como um ponto de ramificação. Então, se temos o código que se parece com isso:

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

Então, o número de estados possíveis é (número de sucursais situadas dentro some_function) ^ 100

Answer 4

Enquanto Josh é certo que você não pode responder a versão mais liberal deste problema devido à ambiguidade do mesmo, você pode respondê-la se você colocar algumas limitações em seu cenário. Há uma grande diferença entre o estado de seu programa e o estado de entidades empresariais dizer.

Por exemplo, digamos que você tenha uma aplicação orientada fluxo de trabalho que é definido por um DFA (State Machine). Você realmente poderia, então, associar um determinado ponto no que DFA com uma identificação de algum tipo.

Então, sim, é tratável mas não sem restrições.

Answer 5

Isto é feito no nível de função; é uma técnica chamada memoization .

Answer 6

estruturas de Kripke de Investigação e lógica modal. Esta é uma abordagem adotada em programas de modelagem. I esquecer o que os sistemas clássicos que utilizam esta abordagem são.