정지 문제

정지 문제(halting problem)는 어떤 프로그램이 주어진 입력에 대해 언젠가 실행을 끝내는지, 아니면 영원히 실행되는지 판정하는 고전적인 결정 문제다. 앨런 튜링은 1936년에 임의의 프로그램과 입력 쌍에 대해 이 판정을 항상 해내는 방법이 없음을 증명했다. 이 문제에서는 범위를 좁힌다. 아래에 정의한 간단한 언어로 작성된 프로그램과 그 프로그램에 넘길 입력이 주어질 때, 프로그램이 멈추는지 판정하고 멈춘다면 어떤 값을 반환하는지 구한다.

이 언어는 0 이상 999 이하의 정수만 다룬다. 그래서 999의 다음 값은 0이고 0의 이전 값은 999다. 변수는 R0부터 R9까지 열 개다. R0에는 프로그램을 호출할 때 넘긴 값, 즉 입력 파라미터가 대입되고, R9에는 항상 출력 값인 반환값이 대입된다. 실행이 시작될 때 R0은 입력 파라미터를 받고 나머지 변수는 모두 0이다.

기본 연산은 대입 MOV, 덧셈 ADD, 뺄셈 SUB, 곱셈 MUL, 정수 나눗셈 DIV, 정수 나눗셈의 나머지 MOD다. 문법은 모두 명령 피연산자1,피연산자2이고 쉼표와 피연산자 사이에 공백이 없다. 피연산자1은 변수 열 개 중 하나이며, 피연산자2는 변수이거나 0 이상 999 이하의 정수다. 모든 기본 연산은 피연산자1의 값을 바꾼다. 그래서 MOV R4,100은 R4에 100을 대입하고, MUL R3,R8은 R3에 R8을 곱한 값을 R3에 대입한다. 덧셈, 뺄셈, 곱셈의 결과는 1000으로 나눈 나머지로 줄인다. DIV와 MOD는 피연산자2가 0이면 0을 저장한다. 즉 DIV R4,0은 MOV R4,0과 같다. 정수 나눗셈은 몫의 정수 부분만 남긴다. 예를 들어 7을 2로 나눈 정수 나눗셈은 3이고 나머지는 1이다.

조건 분기 명령은 여섯 개다. IFEQ는 같은지, IFNEQ는 다른지, IFG는 큰지, IFL은 작은지, IFGE는 크거나 같은지, IFLE는 작거나 같은지 검사한다. 문법은 모두 명령 피연산자1,피연산자2이고, 두 피연산자 모두 변수이거나 0 이상 999 이하의 정수다. 그래서 IFEQ R4,123은 R4가 123과 같은지 검사한다. 조건이 참이면 프로그램은 바로 다음 줄부터 계속 실행한다. 조건이 거짓이면 이 조건 분기 명령과 짝을 이루는 ENDIF의 다음 줄로 건너뛴다. 조건 블록은 중첩될 수 있으므로, 짝이 되는 ENDIF는 중첩된 블록을 세면서 찾는다. 모든 조건 분기 명령에는 짝이 되는 ENDIF가 하나씩 있다.

마지막으로 CALL과 RET이 있고 문법은 둘 다 명령 피연산자다. 피연산자는 변수이거나 0 이상 999 이하의 정수다. CALL은 피연산자의 값을 입력 파라미터로 넘겨 같은 프로그램을 다시 호출한다. 즉 새로 시작한 프로그램의 R0에 그 값이 들어간다. RET은 실행을 끝내고 피연산자의 값을 출력 값으로 반환한다. 프로그램의 마지막 줄은 항상 RET이다. CALL로 프로그램이 자기 자신을 호출한 뒤 실행이 돌아오면, R9에는 호출된 쪽이 반환한 값이 들어 있다. R0부터 R9까지는 모두 지역 변수여서 새로 호출된 프로그램이 호출한 쪽의 변수 값을 바꾸지 못한다. 반환값을 받는 R9만 예외다.

다음은 팩토리얼을 계산하는 프로그램이다.

1번 줄: R0이 0인지 검사한다. 참이면 다음 줄을 실행하고, 거짓이면 짝이 되는 ENDIF의 다음 줄인 4번 줄로 건너뛴다.

2번 줄: 1을 프로그램의 출력 값으로 반환한다.

3번 줄: 1번 줄에서 시작한 조건 블록의 끝을 표시한다.

4번 줄: R0의 값을 R1에 대입한다. R1 ← R0.

5번 줄: R1에서 1을 뺀다. R1 ← R1 - 1.

6번 줄: R1을 입력 파라미터로 넘겨 프로그램을 호출한다.

7번 줄: 앞의 호출이 반환한 R9의 값을 R2에 저장한다. R2 ← R9.

8번 줄: R2에 R0을 곱한다. R2 ← R2 * R0.

9번 줄: R2의 값을 프로그램의 출력 값으로 반환한다.

명령을 정리하면 다음과 같다.

입력은 여러 개의 테스트 케이스로 이루어진다. 테스트 케이스는 50개 이하다. 각 테스트 케이스의 첫 줄에는 정수 두 개 $L$과 $N$이 주어진다. $L$은 프로그램의 줄 수이고, $N$은 프로그램에 넘길 입력 파라미터의 값이다 ($1 \le L \le 100$, $0 \le N \le 999$). 이어지는 $L$개의 줄에 프로그램이 주어진다. 프로그램은 위에서 정의한 규칙에 맞게 항상 문법적으로 올바르다. 모든 명령과 변수 이름은 대문자로만 쓰인다. 입력의 끝은 $L = N = 0$인 경우로 표시하며, 이 경우는 처리하지 않는다.

각 테스트 케이스마다 한 줄에, 주어진 입력 $N$에 대해 프로그램이 반환하는 출력 값을 정수로 출력한다. 프로그램이 멈추지 않으면 별표 하나 *를 출력한다.