상수 및 변수의 가장 높은 가치에 대해 제한된 GoTo 언어에 대해 제한된 중단 문제가없는 이유는 무엇입니까?

Question

이것은 내 대학의 오래된 시험에서 사용하고있는 시험에서 나 자신을 준비하기 위해 사용하고 있습니다 :

주어진 언어 $ \ text {goto} _ {17} ^ c \ substeq \ text {goto} $ . 이 언어에는 $ \ text {goto} $ 프로그램> $ 17 $ 17 $ $ c $ 위의 변수도 없습니다.

$ goto $ 여기에 $ goto $ 언어로 작성된 모든 프로그램 세트를 설명합니다 다음 요소 중 :

변수 $ v_i \ in \ mathbb {n} $ 및 상수 $ c \ in \ mathbb {n} $
할당 : $ x_i := c, x_i := x_i \ pm c $
조건부 점프 : (비교) $ l_i $ HaltCommand : Halt

나는 현재 증명의 공식화로 어려움을 겪고 있지만, 이것은 내가 지금까지 왔던 것입니다. 이 세트에서 주어진 프로그램의 경우 우리는 그것이 유한하다는 것을 알고 있습니다. 유한 프로그램은 유한 양의 변수와 유한 양의 상태 또는 인정 된 상태를 포함합니다. 따라서이 프로세스가 될 수있는 유한 양의 구성이 있습니다. 이 프로그램을 실행하면 우리가 본 모든 구성 목록을 유지할 수 있습니다. 즉, 사용 된 모든 변수 값과 프로그램의 상태의 조합입니다. 우리가 프로그램을 실행하면 결국 두 가지 일 중 하나가 있어야합니다. 프로그램이 중지됩니다. 이 경우 예를 들어 반환하고 그게 멈추기로 결정했습니다. 프로그램은 이전에 기록 된 구성에 도달합니다. 언어가 결정적이지 만, 이것은 우리가 지금 정확히 반복 할 전체 루프를 갔어야 함을 의미합니다.

다른 경우에는 구성을 반복하지 않고도 유한 코드에서 영원히 계속 실행되는 것을 의미합니다. 즉, 모든 단계 후에, 무한 단계 목록 중에서 새로운 구성이 있습니다. 이것은 모순인 무한한 구성이 있음을 의미합니다.

이게 정확합니까? 또한 더 공식적인 증거가 어떻게 될까요? 그렇지 않다면 정확한 증거가 어떻게 보입니까?

Answer 1

다양한 상태 (변수 및 프로그램 카운터의 값 집합)가 있습니다.귀하의 "제한된 고토 프로그램"은 결정적 인 유한 오토 톤을 설명하는 단지 (지저분한) 방법 일뿐입니다.

또는 그 프로그램 상태가 유한 한 이유로, 가능한 모든 비 루핑 계산 (국가 및 이웃의 그래프의 그래프의 넓이를 검색하는 것과 같은 것으로)을 맵핑 할 수 있습니다.