상태 및 시간 전달 논리 및 프로그램 흐름?

Question

일부 참조 키를 사용하여 응용 프로그램의 가능한 모든 상태를 색인하는 것이 유용한 지 궁금합니다 ...

즉, 우리에게 시작하는 프로그램이 있다고 말하면, 가능한 많은 결과가 있다고 말합니다.

그러나 각 결과가 더 많은 논리 상태를 밟아 달성되면 각 지점 사이의 상태는 상태로 간주되어 키에 매핑됩니다.

대규모 프로그램에서 많은 메모리가 필요할 수 있지만 키에 직접 액세스 할 수 있다면 (키는 시간 또는 논리 깊이를 기준으로 할 수 있음) 전체 프로세스를 시작하지 않고도 가능한 상황을 즉시 통과 할 수 있습니다. 새로운 데이터로 다시.

어린이가없는 노드가 최종 결과 인 나무처럼 생각하고 노드와 부모 또는 자녀 사이의 모든 지점은 '상태'입니다. 따라서 프로세스의 잎이 8 개나 최종 결과가 있지만, 어린이가 부족하기 전에 논리가 나무를 얼마나 깊게 내려가는지에 따라 많은 '상태'가있을 수 있습니다.

아마도 시뮬레이션의 경우에는 많은 메모리가 필요합니다.

Answer 1

라이언, 대답은 확실히 그렇습니다.

첫 번째 대답과는 달리, 중단 문제는 아무것도 증명하지 않습니다. 사실, Ryan, 당신이 제안하는 것은 중단 문제를 증명합니다. 잘못된 실제 디지털 컴퓨터에는 적용되지 않으며이 예를 이전의 증거로 사용했습니다.

결정 론적 디지털 시스템 (즉, 실제 디지털 하드웨어에서 실행되는 프로그램)에서 가능한 상태의 수는 유한하므로 가능한 모든 상태가 열거됩니다.

해시에 필요한 정확한 메모리는 다음과 같습니다.

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

초기 상태는 해시 키이고 최종 상태는 해시 값이며 각 초기 상태에 대한 키/값 쌍이 있습니다.

운영 체제의 경우 "프로그램 상태 크기"는 2^(모든 시스템 장치에서 메모리의 총 기가비트)입니다. 분명히, 이러한 대규모 범용 프로그램은 해시에 실용적이지 않은 메모리를 요구할 것이며, 시스템은 자체 추천/돌이킬 수 없을 정도로 복잡하기 때문에 유용하지 않을 것입니다 (즉, 다음 사용자 입력은 이전 시스템 출력에 따라 다름).

설명:

가능한 모든 초기 상태를 색인하고 종료 상태와 연결하면 모든 프로그램의 실행 시간을 0으로 효과적으로 가져 오기 때문에 이것은 매우 유용합니다! 제로 씩 나는 매우 빠른 O (1) 러닝 타임 - 종료 상태를 찾는 데 걸리는 시간 (종료되는 경우)을 의미합니다.

가능한 모든 주에서 시작하여 프로그램을 운영하면주기를 보여주는 일종의 상태 맵을 제공합니다. 따라서 가능한 초기 상태가 주어지면 3 개 (실제로 4 개의 붕괴) 가능성이 있기 때문에 정지 문제가 해결됩니다.

1. 이 프로그램은 가능한 모든 상태를 소진하기 전에 이전에 만난 상태 (초기 상태 이후)를 다시 입력하여 논리적으로 영원히 반복 할 것입니다.
2. 이 프로그램은 이전에 만난 상태를 다시 방문하거나 가능한 모든 상태 (초기 상태 이후)를 소진하기 전에 "종료"로 식별 된 상태에 도달합니다.

3. 또는 4. 가장 단순한 프로그램은 초기 상태에서 시작하여 모든 가능한 상태를 정확히 한 번 입력 한 다음 (3) 이전에 만난 상태와 루프를 영원히 중단하거나 (4) 선택할 수 없습니다.

   for (int i = 0; true; i ++); // 최대 값에 도달하고, 다시 롤오버를 0으로 롤오버합니다.

따라서 기본적으로 귀하의 색인은 다음과 같이 설명 될 수 있습니다.

• 각 초기 상태에 대해 정확히 하나 또는 0 종단 상태가 있습니다.

다시 말해, 각 초기 상태에 대해, 프로그램은 종료 상태에 도달하거나 초기 상태 이후 이미 겪고있는 상태가 끝나고 순환 된 상태로 끝없이 순환합니다.

따라서 실행되는 모든 프로그램의 경우 결정적인 디지털 하드웨어, 그것은이다 절대적으로 가능합니다 (그러나 종종 실용적이지 않습니다) 모든 상태와 그것이 영원히 멈추거나 반복하는지 여부를 결정합니다.

• 실용성은 당신이 가지고있는 유효한 초기 상태의 수에만 달려 있습니다 (감소 할 수 있습니다. 크게 입력 제약 조건) 및 각각의 프로그램이 해시 테이블에 해석 상태를 종료하고 저장하는 데 시간을내는 것이 얼마나 가능합니까?

프로그램의 실행 시간을 강요하는 것 외에 O (1) 운영 외에도 캡처 상태의 기타 사용은 게임 콘솔 에뮬레이터의 저장 상태 기능과 컴퓨터의 최대 절전 모드 기능 (일부 시스템 메모리를 사용해야하므로 완벽한 상태는 아니지만 상태의 완벽한 복원은 아니지만 일부는 상태를 사용해야합니다. 상태를 복원하는 코드의 경우 일부 메모리가 저장되지 않을 수 있습니다 (예 : GPU 메모리).

이것이 증명하는 것은 모든 프로그램이 해시 테이블로 표시 될 수 있다는 것입니다. 모든 프로그램은 초기 대표 상태 전환 맵으로 표시 될 수 있습니다.모든 프로그램은 대규모 메모리 발자국으로 하나의 큰 기능으로 단순화 될 수 있습니다!

Answer 2

이것은 일반 프로그램을 위해 해결할 수 없습니다. 중단 문제는 프로그램이 중단 될지 여부를 결정하는 것이 불가능하다는 것을 증명합니다. 주어진 상태가 가능한지 여부를 결정하는 문제는 정지 문제로 환원 될 수 있으므로 해결할 수 없습니다.

Answer 3

나는이 접근법이 완전히 다루기 어려울 것이라고 생각합니다.

검색 문제로서 너무 큽니다. 각 주가 10 개의 결과로 이어질 수 있다고 가정한다면 (이 숫자는 실제로 낮다고 생각하지만) 20 발 앞서 앞서 보려면 200 억 가능성을 추적해야합니다.

루프의 모든 단계는 분기점으로 간주됩니다. 따라서 다음과 같은 것처럼 보이는 코드가있는 경우.

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

그런 다음 가능한 상태의 수는 (some_function 내부의 지점) ^ 100입니다.

Answer 4

조쉬가 모호성으로 인해이 문제의 가장 자유로운 버전에 대답 할 수 없다는 것이 옳지 만 시나리오에 약간의 제한 사항을 제한하면 대답 할 수 있습니다. 프로그램 상태와 사업체의 상태 사이에는 큰 차이가 있습니다.

예를 들어, DFA (State Machine)에 의해 정의 된 워크 플로 지향 응용 프로그램이 있다고 가정 해 봅시다. 그런 다음 실제로 해당 DFA의 주어진 점을 어떤 종류의 ID와 연결할 수 있습니다.

그렇습니다. 그것은 다루기 쉬지만 제한이없는 것은 아닙니다.

Answer 5

이것은 함수 레벨에서 수행됩니다. 그것은 불리는 기술입니다 메모 화.

Answer 6

Kripke 구조 및 모달 논리를 연구하십시오. 이것은 모델링 프로그램에서 취한 접근법입니다. 이 접근법을 사용하는 고전적인 시스템이 무엇인지 잊어 버립니다.