튜링 머신의 누락된 단계
이진수에 1을 더하는 튜링 머신을 설계하려고 합니다. 이 기계는 오른쪽에서 왼쪽으로 숫자를 처리하며, 다음 규칙을 따릅니다:
- 가장 오른쪽 비트부터 시작해요.
- 현재 비트가 0이면: 1로 뒤집고 멈춰요.
- 현재 비트가 1이면: 0으로 뒤집고(1 + 1은 올림이 발생하므로) 왼쪽으로 이동해 다음 비트를 처리해요.
- 왼쪽으로 이동했을 때 가장 왼쪽 자릿수를 넘어 공백을 만나면: 올림을 나타내기 위해 1을 쓰고 멈춰요.
아래 상태도는 이 과정을 표현하려 하지만, 중요한 전이가 하나 빠져 있습니다. 누락된 단계를 찾아보세요.
이 연습은 강의의 일부입니다
