Turing Machine

https://youtu.be/E3keLeMwfHY?si=xfBwvHh_L6XnVX8a

---

 

이글을 보기전에 다음 동영상을 보길 권함:

https://youtu.be/-ZS_zFg4w5k?si=_WvPsGJlw_LUm2_j

---

0. Turing Machine과 계산 가능성 (computability) 

Turing Machine (튜링 기계)

• Alan Turing 이 1936년에 제안한
• 추상적인 계산 모델 (abstract model of computation) 임.

실제 computer 의 물리적 구조를 묘사하기 위한 장치가 아니라, 다음과 같은 질문을 수학적으로 다루기 위해 제안됨.

어떤 문제를
algorithm 으로 계산할 수 있는가?

Algorithm (알고리즘)

• 어떤 문제를 해결하기 위해 수행해야 할 유한한 단계의 명확한 절차임.
• 각 단계에서 무엇을 해야 하는지가 명확하게 정해져 있어야 함.
• 같은 입력에 대해 정해진 규칙에 따라 계산을 진행함.

좀 더 쉽게 말하면,

• algorithm 은 문제를 해결하기 위한 명확한 계산 절차임.
• 어떤 계산이 algorithm 으로 수행 가능하다는 것은, 그 절차를 수행하는 Turing Machine 을 만들 수 있다는 것과 같은 의미로 봄.
• 따라서 어떤 문제가 computable (계산 가능) 하다는 것은, 그 문제를 해결하는 algorithm 을 Turing Machine 으로 표현하여 실행할 수 있다는 의미임.

결국 알고리즘은 오늘날 컴퓨터에선 프로그램으로 구현되는게 일반적임.

참고로,
여기서 Computation (계산) 은 정해진 rule 에 따라 input 과 state 를 단계적으로 변환하여 결과를 만들어내는 과정임.

---

 

Turing Machine 은 매우 단순한 구조를 가지지만,

algorithm 으로 수행할 수 있다고 생각되는 일반적인 계산을 표현 (=실행)할 수 있음.

(어떤 문제가 algorithm으로 풀 수 있다면, Turing machine은 해당 문제를 풀 수 있음)

 

이러한 이유로 computability theory (계산 가능성 이론) 의 가장 기본적인 계산 모델로 사용됨.

 

좀 더 쉽게 애기하면

• 어떤 계산이 algorithm 으로 수행 가능하다는 것은,
  그 계산을 수행하는 Turing Machine 을 만들 수 있다는 것과 같은 의미로 봄.
• 어떤 문제가 계산 가능(computable)하다는 것은
  그 문제를 해결하는 algorithm을 Turing Machine으로 표현하여 실행할 수 있다는 의미임.

 

참고: Turing, A. M. (1936). “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society, Series 2, 42, 230–265.

• 1928년: David Hilbert와 Wilhelm Ackermann이 Grundzüge der Theoretischen Logik에서 Entscheidungsproblem (결정 문제, Decision Problem) 을 제시
  • 형식 논리의 임의의 명제가 주어졌을 때, 그것이 논리적으로 참인지 여부를 기계적인 절차(algorithm)만으로 항상 판정할 수 있는가?
  • 즉, 임의의 논리 명제의 validity를 항상 판정할 수 있는 일반적인 decision procedure가 존재하는가? : 수학자가 하던 일.
• 1936년: Alan Turing이 이 문제를 다루기 위해 Turing Machine 개념을 제안하고, 일반적인 결정 절차가 존재하지 않음을 보임.
  • 모든 논리적 문제의 참·거짓을 유한한 계산 절차로 항상 판정해 주는 범용 algorithm 은 존재하지 않음.
• 1937년: Turing의 논문 On Computable Numbers, with an Application to the Entscheidungsproblem 이 정식 출판됨

 

1936년 Turing이 증명한 것은 다음과 같음:

• 어떤 특정 문제는 algorithm 으로 해결할 수 있음.
• 하지만 모든 문제를 대상으로
  • input 을 넣으면
  • 유한한 시간 안에
  • 반드시 정답을 내는
  • 하나의 universal decision algorithm
    은 만들 수 없음.

---

---

참고: Turing Machine과 Imitation Game

 

Turing 은 다음과 같은 당시 어려운 두 문제 에 대해 비슷한 접근을 취하여 정의함:

• 무엇이 계산 가능한가? = 어떤 문제를 algorithm으로 해결할 수 있는가?
• 기계가 생각할 수 있는가? = machine intelligence를 어떻게 판정할 수 있는가?

추상적이고 정의하기 어려운 개념을 직접 정의하기보다, 관찰 가능하고 판정 가능한 절차로 바꿈.

 

계산 가능성에서는:

“algorithm 으로 계산 가능하다”
=> “Turing Machine 으로 계산할 수 있는가?”

 

Imitation Game 에서는:

“machine 이 생각하는가? (machine이 지능을 가지고 있는가?)”
=>“대화만으로 인간과 machine 을 신뢰성 있게 구별할 수 있는가?”

 

따라서 Imitation Game 은

• intelligence 자체의 정의라기보다,
• intelligence 를 행동을 통해 평가하려는 operational test로 보는 것이 정확함.

 

Imitation Game은 Turing의 1950년 논문 Computing Machinery and Intelligence 에서 제시된 실험 설정임:

• 심사자가 text-based conversation 만으로
• 상대가 human 인지 machine 인지 구별하려고 함.
• machine 이 인간과 충분히 구별되지 않는다면 intelligent behavior 를 보인 것으로 간주함.

이는 오늘날 Turing Test로 불리며, 이는 Imitation Game의 개념을 일반화하여 부르는 이름임.

 

참고: Alan M. Turing (1950), “Computing Machinery and Intelligence.” Mind, Volume LIX, Issue 236, October 1950, pp. 433–460.

 

https://dsaint31.me/mkdocs_site/ML/ch00/ch00_00_intro/?h=turing#turing-test

BME

---

1. Automaton 관점에서의 Turing Machine

automaton (오토마톤) 은
입력을 읽고
현재 state 와 정해진 transition rule 에 따라
동작하는 추상적인 machine 임.

일반적으로 다음 요소를 가짐.

• 입력을 읽음.
• 유한한 수의 내부 state (상태) 를 가짐.
• 정의된 transition rule (전이 규칙) 에 따라 state 를 변경함.
• 특정 state 에 도달하면 계산을 종료하거나 결과를 결정함.

https://ds31x.tistory.com/626#2.-%EA%B3%84%EC%82%B0-%EC%9D%B4%EB%A1%A0%EC%97%90%EC%84%9C%EC%9D%98-machine

Machine 이란?

---

Finite Automaton vs. Turing Machine

Finite Automaton (유한 오토마톤) 과 Turing Machine 의 핵심적인 차이는 사용할 수 있는 memory 에 있음.

	Finite Automaton	Turing Machine
control state	유한	유한
memory	현재 state 에 사실상 제한됨	무한히 확장 가능한 tape
read/write	입력을 읽음	tape 를 읽고 쓸 수 있음
이동	일반적으로 입력을 한 방향으로 처리	head 가 좌우로 이동 가능
계산 능력	제한적	일반적인 algorithm 표현 가능

 

Finite Automaton

• 입력 길이에 따라 증가하는 별도의 memory 를 사용할 수 없음.
• 따라서 이미 읽은 입력 전체를 저장하거나 임의의 위치로 돌아가 수정하는 작업을 수행할 수 없음.

반면 Turing Machine 은 읽고 쓸 수 있는 tape (테이프) 를 memory 로 사용함.

• tape 는 이론적으로 무한히 확장 가능함.
• head 는 tape 의 symbol 을 읽을 수 있음.
• 새로운 symbol 을 기록할 수 있음.
• 왼쪽 또는 오른쪽으로 이동할 수 있음.
• 이미 지나간 위치로 돌아가 다시 읽거나 수정할 수 있음.

주의할 점은 Turing Machine 의 state 수가 무한한 것이 아니라는 것임.

Turing Machine
= finite control state + unbounded tape memory

 

즉,
유한한 state 를 가진 automaton 에
읽고 쓸 수 있는 무한히 확장 가능한 memory 를 결합한 계산 모델이

Turing Machine임.

---

2. Turing Machine의 기본 구성

Turing Machine 은 엄밀하게 다음과 같은 7-tuple 로 정의할 수 있음.

$$
M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{accept}},q_{\mathrm{reject}})
$$

where

• $Q$: 유한한 state 집합
• $\Sigma$: input alphabet (input 에 사용가능한 symbol의 집합)
• $\Gamma$: tape alphabet (tape에 기록가능한 symbol의 집합), input symbol도 tape에 기록되어야 하므로, $\Sigma \subseteq \Gamma$임.
• $\delta$: transition function
• $q_0$: initial state
• $q_{\mathrm{accept}}$: accept state
• $q_{\mathrm{reject}}$: reject state

그리고 개별 symbol (보통 0,1만 사용하는 예가 대다수) 과 alphabet 을 구별하면 다음과 같음:

• $a \in \Sigma$: 하나의 input symbol
• $b \in \Gamma$: 하나의 tape symbol

개념적으로는 다음 네 가지가 핵심임:

구성 요소	설명
Tape	symbol 을 저장하는 memory. cell 단위로 구성되며 이론적으로 무한히 확장 가능함.
Head	현재 tape cell 의 symbol 을 읽거나 쓰거나 지울 수 있고, 왼쪽 또는 오른쪽으로 이동함.
State	machine 의 현재 내부 상태를 나타냄.
Transition Function	현재 state 와 읽은 symbol 에 따라 다음 state, 기록할 symbol, head 이동 방향을 결정함.

 

transition function 은 일반적으로 다음 형태를 가짐.

$$
\delta(q,a)=(p,b,D)
$$

where

• $q$: 현재 state
• $a$: 현재 head 가 읽은 symbol
• $p$: 다음 state
• $b$: tape 에 새로 기록할 symbol
• $D \in {L,R}$: head 의 이동 방향

따라서 하나의 transition 은 다음 동작을 의미함.

$$
\text{현재 state}+\text{읽은 symbol}
\longrightarrow
\text{새 state}+\text{기록할 symbol}+\text{head 이동}
$$

Turing Machine 의 computation 은

• 초기 input 이 기록된 tape 에서 시작하여
• 이 transition 을 반복적으로 수행하는 과정임.

---

3. Program으로서의 Machine Description

일반적인 Turing Machine $M$에서는 transition function $\delta$가 machine 자체에 고정되어 있음.

 

따라서 다음 두 요소를 구분할 수 있음:

---

Machine Description : $\langle M \rangle$

machine 자체를 정의한 description 임.

 

대표적으로 다음 정보를 포함함.

• state 집합
• input alphabet
• tape alphabet
• transition function
• initial state
• accept / reject state

즉, 어떤 automaton 인가를 정의하는 정보임.

---

Input : $x$

정의된 machine $M$에 실제로 주어지는 input data 임.

 

따라서 일반적인 Turing Machine 의 계산은 개념적으로 다음 구조임.

고정된 Machine M + Input x
              ↓
             M(x)

여기서 transition function 은 일종의 program (or S/W) 역할을 함.

즉, 일반적인 Turing Machine 에서는 program 은 machine 에 고정되어 있고 input 만 변경됨.

---

4. Universal Turing Machine (UMT)

Universal Turing Machine, UTM (보편 튜링 기계) 은

• 임의의 다른 Turing Machine 을
• simulation 할 수 있도록 구성된 Turing Machine 임.

일반 Turing Machine 과 가장 중요한 차이는 다른 machine 의 description 자체를 input 으로 받는다는 점임.

 

입력은 개념적으로 다음과 같이 구성됨.

$$
\langle M\rangle, x
$$

where

• $\langle M\rangle$: simulation 할 Turing Machine $M$의 encoded description
• $x$: 해당 machine $M$에 제공할 실제 input

즉,

• $\langle M\rangle$은 어떤 automaton 을 실행할 것인가를 알려줌.
• $x$는 그 automaton 에 어떤 input 을 줄 것인가를 알려줌.

Universal Turing Machine $U$는 $\langle M\rangle$에 기록된 transition rule 을 해석하면서 $M$의 computation 을 단계별로 simulation 함.

 

개념적으로 다음과 같음.

$$
U(\langle M\rangle,x)=M(x)
$$

 

Automaton 관점에서는 다음과 같이 이해할 수 있음.

Universal Turing Machine 은
다른 Turing Machine 의 transition system 을 data 로 받아
해당 automaton 의 동작을 simulation 하는 automaton 임.

---

5. Program을 Data로 다룬다는 의미

Universal Turing Machine 의 중요한 점은
machine description 자체를 symbol 로 encoding 할 수 있다는 것임.

 

즉,

transition rule,
즉 program 자체를 data 로 표현할 수 있음.

 

일반적인 Turing Machine 에서는 transition rule 이 machine 에 고정되어 있음.

 

반면 Universal Turing Machine 에서는 실행할 machine 의 transition rule 이 input 의 일부가 됨.

[ Machine Description <M> ] ┐
                            ├──> [ Universal Turing Machine ] ──> Result
[ Input x ]                 ┘

 

이 구조는 현대 computer (Stored Program Computer or 폰노이만 구조)의 다음 개념과 매우 유사함.

[ Program ] ┐
            ├──> [ Memory ] ──> [ Processor ] ──> Result
[ Data    ] ┘

 

즉 동일한 hardware 에 서로 다른 program 을 memory 에 적재함으로써 완전히 다른 계산을 수행할 수 있음.

• word processor
• web browser
• compiler
• database
• neural network program

등이 동일한 general-purpose computer 에서 실행될 수 있는 것도 이러한 program-as-data 관점과 연결됨.

• Universal Turing Machine 과 현대의 stored-program computer 는 동일한 개념은 아니지만,
• program 을 encoding 된 data 로 저장하고 범용 machine 이 이를 실행한다는 점에서 중요한 이론적 연결 관계를 가짐.

https://ds31x.tistory.com/384#%EC%B0%B8%EA%B3%A0-stored-program-computer

[CE] EDSAC과 EDVAC, 그리고 Stored Program Computer

 

---

6. Turing Completeness

Turing Completeness (튜링 완전성) 는

• 어떤 computational system 이
• Turing Machine 으로 계산 가능한 모든 계산 을 표현하고 수행할 수 있는 계산 능력을
• 가지고 있음을 의미함.

즉

• 어떤 system 이 임의의 Turing Machine 의 computation 을 simulation 할 수 있다면
• 해당 system 을 Turing-complete 하다고 함.

 

이를 Universal Turing Machine 과 구분하면 다음과 같음.

• Universal Turing Machine
  • 다른 Turing Machine 을 simulation 하도록 구성된 특정 machine
• Turing-complete system
  • 그러한 simulation 을 수행할 수 있는 수준의 computational power 를 가진 system

현대의
대부분의 general-purpose programming language 는
이론적으로 Turing-complete 함.

예:

• C
• Python
• Java
• Rust

https://ds31x.tistory.com/427#%EC%B0%B8%EA%B3%A0-turing-completeness-%EC%99%80-control-structure

[Programming] Control Flow 와 Control Structure

 

단, 실제 computer 는 memory 가 유한하므로 문자 그대로 무한한 tape 를 가지는 Turing Machine 과 동일하지 않음.

 

때문에, Turing completeness 를 논할 때에는

일반적으로 필요에 따라 memory 를 임의로 확장할 수 있다는 이상화된 조건을 가정함.

 

또한 Turing completeness 는 performance 를 의미하지 않음에 주의할 것.

Turing-complete 하다는 것은
계산을 얼마나 빠르게 수행하는지가 아니라,
어떤 종류의 계산을 원리적으로 표현할 수 있는가를 의미함.

---

7. Computability와 Decidability

Turing Machine 이 중요한 이유는 단순히 강력한 계산 모델이기 때문만이 아님.

이를 이용하면
계산 가능한 것과 계산 불가능한 것의 경계를
수학적으로 정의할 수 있음.

---

Turing-computable

어떤 function 을 계산하는 Turing Machine 이 존재한다면
해당 function 을 Turing-computable (튜링 계산 가능) 하다고 함.

즉,

어떤 algorithm 으로 계산할 수 있다는 개념을
Turing Machine 의 존재 여부로 형식화한 것임.

---

Decidable

어떤 decision problem 에 대해

• 모든 input 에서 반드시 정지하여 올바른 Yes/No 답을 반환하는 Turing Machine 이 존재하면 (Hibert의 질문에 기인)
• 해당 문제를 decidable (결정 가능) 하다고 함.

반대로 그러한 machine 이 존재하지 않는 문제를
undecidable (결정 불가능) 하다고 함.

 

따라서 Turing Machine은

• computation 의 가능성을 설명하는 동시에
• algorithm 이 원리적으로 해결할 수 없는 문제도 존재함을 보여주는 도구가 됨.

 

---

8. Halting Problem

대표적인 undecidable problem 이 Halting Problem (정지 문제) 임.

(Hilbert에 대한 Turing의 답은 No!)

 

문제는 다음과 같음.

임의의 program $M$과 input $x$가 주어졌을 때,
$M(x)$가 언젠가 정지하는지 아니면 영원히 실행되는지를
모든 경우에 정확하게 판별하는 algorithm 이 존재하는가?

그러한 판별 machine 을 $H$라고 가정해 봄.

$$
H(\langle M\rangle,x)=
\begin{cases}
\mathrm{True}, & M(x)\text{가 정지하는 경우} \\
\mathrm{False}, & M(x)\text{가 정지하지 않는 경우}
\end{cases}
$$

이제 $H$를 이용하여 새로운 machine $D$를 구성함.

(이 $D$는 "같이보면 좋은 자료" 의 youtube 동영상에선 Bizarro 로 이름이 붙여짐= "정반대의, 왜곡된, 기괴한")

https://youtu.be/7TycxwFmdB0?si=Ap89opYYfE1k_FVo&t=395

 

$D$는 machine description $\langle M\rangle$을 입력받고 다음과 같이 동작함.

1. $H(\langle M\rangle,\langle M\rangle)$을 실행함.
2. $H$가 "정지함"이라고 판정하면 무한히 실행함.
3. $H$가 "정지하지 않음"이라고 판정하면 즉시 정지함.

즉 $H$의 예측과 반대로 행동하도록 $D$를 정의함.

 

이제 $D$ 자신의 description 을 $D$에 입력함.

$$
D(\langle D\rangle)
$$

 

두 경우를 생각할 수 있음.

• $D(\langle D\rangle)$가 정지한다고 가정
  • $H$는 정지한다고 판정해야 함.
  • 그러나 $D$의 정의에 따라 $D$는 무한히 실행함.
  • 모순임.
• $D(\langle D\rangle)$가 정지하지 않는다고 가정
  • $H$는 정지하지 않는다고 판정해야 함.
  • 그러나 $D$의 정의에 따라 $D$는 즉시 정지함.
  • 역시 모순임.

따라서 처음에 가정한 범용 판별 machine $H$는 존재할 수 없음.

 

Halting Problem 은
undecidable 함.

 

위의 내용은 Turing Machine 의 계산 능력이 부족해서 발생하는 문제가 아님.

 

Halting Problem이 undecidable 이라는 것은

• Turing-complete 한 계산 모델 자체에도
• 모든 입력에 대해 항상 정답을 내는 algorithm 을 만들 수 없는 문제가 존재함을 의미함.
• 이는 단순히 계산 시간이나 memory 가 부족해서가 아니라, 무한한 계산 resource 를 허용하더라도 그런 범용 algorithm 자체가 존재하지 않음 (computability에 대한 문제)을 의미함
• 모든 경우에 유한한 단계 안에 halt 여부를 판정하는 algorithm 자체가 존재하지 않는다는 의미임.

---

9. Church–Turing Thesis

Turing Machine 과 computability 를 이해할 때 함께 등장하는 개념이 Church–Turing Thesis (처치–튜링 명제) 임.

 

핵심 주장은 다음과 같음.

직관적인 의미에서 algorithm 으로 계산 가능한 모든 것은
Turing Machine 으로 계산 가능함.

이는 수학적 theorem 이라기보다는

• algorithm 이라는 비형식적인 개념과
• Turing-computable 이라는 형식적인 개념을 동일시하는 thesis 임.

당시 서로 독립적으로 제안된 여러 계산 모델들이 동일한 계산 가능성의 범위를 나타낸다는 사실이 이를 강하게 뒷받침함.

대표적으로 다음 모델들이 동일한 computability 를 가지는 것으로 여겨도 됨:

• Turing Machine
• lambda calculus (먼저 발표되었으나 수학 논문이라 복잡한 편임)
• recursive function
• register machine

오늘날 Turing Machine 은

• 단순히 여러 계산 모델 중 하나라기보다,
• algorithmic computation 의 범위를 정의하는 표준적인 기준 모델로 사용됨.

---

10. 전체 관계

전체적인 관계를 정리하면 다음과 같음.

Finite Automaton
      │
      │ + read/write tape memory
      ▼
Turing Machine
      │
      │ machine description을 data로 encoding
      ▼
Universal Turing Machine
      │
      ├───────> Turing Completeness
      │                 계산 가능한 범위의 기준
      │
      └───────> Computability Theory
                              │
                              ├── Decidable Problems
                              │
                              └── Undecidable Problems
                                      │
                                      └── Halting Problem

---

11. 핵심 정리

1. Turing Machine
   • finite state와 읽고 쓸 수 있는 unbounded tape 를 가진 automaton 임.
   • transition function 을 반복하여 computation 을 수행함.
2. Machine Description
   • state, alphabet, transition function 등 machine 자체를 정의한 정보임.
   • transition function 은 해당 machine 의 program 역할을 함.
3. Universal Turing Machine
   • machine description $\langle M\rangle$과 input $x$를 함께 입력받음.
   • $\langle M\rangle$에 기술된 transition 을 해석하여 $M(x)$를 simulation 함.
   • 즉 program 자체를 data 로 다룰 수 있음을 보여줌.
4. Turing Completeness
   • Turing Machine 으로 계산 가능한 모든 computation 을 수행할 수 있는 computational power 를 의미함.
   • 계산 속도나 효율성이 아니라 계산 가능한 범위에 관한 개념임.
5. Computability와 Undecidability
   • Turing Machine 을 이용하여 algorithm 으로 해결할 수 있는 문제의 범위를 형식적으로 정의할 수 있음.
   • 동시에 Halting Problem 과 같이 어떠한 algorithm 으로도 모든 경우를 해결할 수 없는 문제도 존재함.

Turing Machine 의 가장 중요한 의미는 단순히 하나의 가상 machine 을 제안했다는 데 있지 않음.

 

Turing Machine 은

• algorithm 과 computation 을 수학적으로 정의하고,
• 무엇이 계산 가능하며 무엇이 원리적으로 계산 불가능한지를 구분할 수 있게 만든
• 계산 가능성 이론의 기준 모델임.

---

같이보면 좋은 자료들

https://ds31x.tistory.com/626

Machine 이란?

 

https://dsaint31.me/mkdocs_site/CE/ch08/ce08_programming_language/

BME

 

https://youtu.be/7TycxwFmdB0?si=MffTuIRvumR-SHla