이 튜링 기계는 테이프 상에서 0과 0 사이에 존재하는 1의 개수를 세고, 그 개수가 짝수인 경우에는 1을 하나 추가하여 홀수로 만드는 기능을 수행합니다.
📌 기본 조건
- 심볼: 0, 1, 공백(_)
- 명령어: R (오른쪽), L (왼쪽), P (쓰기), E (종료 상태)
- 입력 예시: 0 1 1 0 → 출력: 0 1 1 1 0 (1이 3개 → 홀수)
🧠 상태 정의
q0: 시작 상태 – 첫 번째 0 찾기q1: 0 이후 1을 탐색q_even: 현재 1의 개수가 짝수 상태q_odd: 현재 1의 개수가 홀수 상태q_write: 0까지 돌아가서 1 삽입할 위치로 이동q_add: 1 삽입 실행qe: 종료
🧾 최종 명령어 구현
(q0, 0) → (0, R, q1)
(q0, 1) → (1, R, q0)
(q0, _) → (_, R, qe)
(q1, 1) → (1, R, q_even)
(q1, 0) → (0, R, qe) // 0 뒤에 1이 하나도 없을 경우
(q_even, 1) → (1, R, q_odd)
(q_even, 0) → (0, L, q_write)
(q_odd, 1) → (1, R, q_even)
(q_odd, 0) → (0, R, qe) // 홀수면 그대로 종료
(q_write, 1) → (1, L, q_write)
(q_write, 0) → (0, R, q_add)
(q_add, 1) → (1, R, q_add)
(q_add, 0) → (1, R, qe) // 짝수 개수였으니 1을 삽입하여 홀수로
💡 요약
- 이 튜링 기계는 매번 첫 번째 0부터 탐색하며
- 0과 0 사이의 1 개수를 홀/짝 상태 전이로 판별하고
- 짝수일 경우 1을 삽입하여 홀수로 만든다
- 그 외 경우는 아무 작업 없이 다음 블록으로 이동
이제 이 논리를 기반으로 수업 과제, 논문, 오토마타 실습에 활용하실 수 있습니다.
