최댓값이 늘지 않는다는 것만으로 종료를 증명할 수 있을까

M(D(a))≤M(a)를 증명하라. 최댓값이 늘지 않는 비음이 아닌 정수이므로 언젠가는 모든 항이 0이 된다는 추론은 충분한가? (0,0,1,1)의 변환과 세 항 (0,1,1)의 변환을 비교한다.

두 항이 모두 0과 M 사이에 있으면 차의 절댓값은 M 이하이므로 변환 후 최댓값은 커지지 않는다. 그러나 (0,0,1,1)에서는 처음 두 변환 동안 최댓값이 계속 1이고 세 번째에야 0이 된다. 엄격히 줄어드는 것이 아니라는 점을 보여 준다. 더 나아가 세 항에서는 (0,1,1)→(1,0,1)→(1,1,0)→(0,1,1)이라는 주기가 생겨 최댓값 1이 계속 유지된다. 따라서 비증가인 정수라는 조건만으로 0 종료를 결론 낼 수 없다. 네 항의 종료를 증명하려면 네 항이라는 구조에 관한 추가 논증이 필요하며, 이 글은 그 보편 종료 증명을 완료했다고 주장하지 않는다.

교사 질문: 약하게 감소하는 양과 일정 횟수 안에 반드시 감소하는 양을 구분해 알고리즘의 종료 근거를 찾아보자.

출처·착안: WiTje: Ducci-rijtjes. 위 문항의 조건·수치·풀이와 교사 질문은 새로 작성했다.