---
title: "튜링 머신: 계산 가능성의 경계를 설명하는 추상 기계"
author: "Lee"
published_at: "2026-10-08T03:00:04.513Z"
updated_at: "2026-09-30T10:02:10.675Z"
tags: ["컴퓨터공학","계산이론"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%ED%8A%9C%EB%A7%81-%EB%A8%B8%EC%8B%A0-%EA%B3%84%EC%82%B0-%EA%B0%80%EB%8A%A5%EC%84%B1%EC%9D%98-%EA%B2%BD%EA%B3%84%EB%A5%BC-%EC%84%A4%EB%AA%85%ED%95%98%EB%8A%94-%EC%B6%94%EC%83%81-%EA%B8%B0%EA%B3%84"
ai_assisted: false
---

# 튜링 머신: 계산 가능성의 경계를 설명하는 추상 기계

[원문](https://ariser.io/@writer_a1cd615ab19e/%ED%8A%9C%EB%A7%81-%EB%A8%B8%EC%8B%A0-%EA%B3%84%EC%82%B0-%EA%B0%80%EB%8A%A5%EC%84%B1%EC%9D%98-%EA%B2%BD%EA%B3%84%EB%A5%BC-%EC%84%A4%EB%AA%85%ED%95%98%EB%8A%94-%EC%B6%94%EC%83%81-%EA%B8%B0%EA%B3%84)

튜링 머신은 유한한 제어 상태, 기호를 읽고 쓸 수 있는 테이프, 테이프 위를 이동하는 헤드로 계산을 표현하는 추상 모델이다. 물리 CPU의 설계도가 아니라 어떤 문제에 알고리즘이 존재하는지 논의하기 위한 정밀한 기준이다.

![단항 숫자 111의 끝에 1을 써 값을 증가시키는 튜링 머신](/api/v1/media/e577b1e5-8dcb-4ad7-9fa7-7d2696a67828)

*튜링 머신은 유한 제어와 확장 가능한 테이프로 알고리즘의 계산 가능성을 모델링한다.*

### 한 단계에서 하는 일

현재 상태와 헤드가 읽은 기호에 따라 새 기호를 쓰고, 왼쪽이나 오른쪽으로 이동하며, 다음 상태로 바뀐다. 상태와 테이프 알파벳은 유한하지만 테이프는 필요한 만큼 사용할 수 있다고 가정한다. 계산의 임시 기억은 이 테이프에 저장된다.

예를 들어 양의 정수를 1의 반복인 단항 표현으로 쓰면 3은 111이다. 오른쪽으로 이동하며 마지막 1 뒤의 빈칸을 찾고 그곳에 1을 쓴 뒤 멈추는 기계는 값을 하나 증가시킨다.

```text
Input tape:  ... blank 1 1 1 blank blank ...
Head starts on the first 1.
State q_scan:
    read 1     -> write 1, move Right, stay q_scan
    read blank -> write 1, move Right, enter q_accept
Output tape: ... blank 1 1 1 1 blank ...
```

이 간단한 예에서는 현재 상태와 읽은 기호만으로 다음 행동이 정해진다. 더 복잡한 기계는 표시용 기호를 써 이미 처리한 위치를 기록하고 여러 번 왕복할 수 있다. 입력 길이에 비례해 항상 한 번만 읽는 모델은 아니다.

### 멈춤과 수락은 다르다

언어 판정에서는 수락 상태와 거절 상태를 구분한다. 입력이 언어에 포함되면 수락하고 포함되지 않으면 거절하며 모두 멈추는 기계가 결정기다. 포함되지 않는 입력에서 영원히 실행할 수도 있는 기계는 인식기가 될 수 있지만 항상 결정을 주지는 않는다.

기계의 상태와 규칙은 유한한 문자열로 부호화할 수 있다. 그래서 다른 튜링 머신의 설명과 입력을 받아 실행을 모사하는 보편 튜링 머신을 생각할 수 있다. 프로그램도 데이터로 다룰 수 있다는 관점이 중요한 결과를 만든다.

여러 테이프, 다른 이동 규칙 같은 변형은 계산 가능한 함수의 범위가 같을 수 있지만 실행 단계 수의 효율은 달라질 수 있다. 계산 가능성의 동등함과 복잡도의 동일함은 같은 주장이 아니다.

무한 테이프는 실제 컴퓨터가 무한 메모리를 가진다는 말이 아니다. 유한한 입력의 계산에 필요하면 얼마든지 더 사용할 수 있다는 이상화다. 실제 하드웨어의 저장 한계와 이론의 알고리즘 존재 여부는 다른 층의 질문이다.

Church–Turing 논지는 효과적으로 계산 가능한 절차를 튜링 계산으로 포착한다는 원리다. 수학적 모델끼리의 동등성 정리와는 구분해야 한다. 이 모델을 통해 일반적인 정지 판정의 불가능성이나 P·NP 같은 계산 복잡도 개념을 엄밀하게 정의할 수 있다.

복잡도를 분석할 때는 테이프의 입력 부호화와 한 단계의 연산을 정해야 한다. 같은 숫자를 단항으로 쓰면 입력 길이가 숫자 값에 비례하고, 이진으로 쓰면 로그에 비례한다. 표현 선택을 숨기면 실행 단계 수의 비교도 달라진다.

### 참고 자료

- [MIT OpenCourseWare · Automata, Computability, and Complexity](https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/)