프로그래밍 언어 4장 튜링머신

4. 튜링 머신

튜링 머신: 알고리즘을 실행하는 수학적 모델

언어의 계층 구조

총 3가지로 나뉜다.

1. 정규 언어
   • 3가지 중 가장 적은 표현이 가능하다.
   • 정규 언어는 정규 표현식(regular expression)이라는 특별한 형식으로 표현될 수 있다.
2. 컨텍스트-프리 언어
   • 정규 언어보다는 많은 표현이 가능하다.
   • 컨텍스트-프리 언어는 특별한 유형의 문법인 컨텍스트-프리 문법을 사용하여 생성된다.
3. 튜링 머신
   • 정규 언어와, 컨텍스트-프리 언어를 표현할 수 있다.
   • 형식 언어의 가장 강력한 종류 중 하나인 계산 가능 언어(computable language)다.

튜링 머신의 등장 배경

• 모든 명제들의 참/거짓을 “기계적으로” 판명할 수 없을까?
• 참인 모든 명제들을 “기계적으로” 만들어낼 수 없을까?

위 조건에 부합하는게 바로 튜링 머신임

튜링이 정의한 기계적

그림 구성 요소

1. 테이프 (Tape): 무한대의 저장 공간으로, 각 칸은 0 또는 1과 같은 심볼을 담을 수 있습니다.
2. 테이프 헤드 (Tape Head): 테이프에서 현재 위치를 가리키는 역할을 합니다. 헤드가 가리키는 칸에 저장된 심볼을 읽거나 쓸 수 있습니다.
3. 제어 유닛 (Control Unit): 튜링 머신의 동작을 제어합니다. 제어 유닛은 현재 상태를 나타내는 상태 레지스터와, 규칙 테이블을 참조하여 다음 동작을 결정하는 규칙 레지스터를 포함합니다.
4. 규칙 테이블 (Rule Table): 현재 상태와 읽은 심볼에 대한 다음 상태, 쓸 심볼, 헤드를 이동시킬 방향 등을 결정합니다.

그림 풀이

1. 현재 기계의 상태는 A이고, 읽은 기호는 *이므로 *을 그대로 *로 쓰고 두 번째 칸으로 헤드를 옮기며 기계의 상태를 A라 둔다.
2. 두 번째 칸에서 기계의 상태는 A이고, 읽은 기호는 $이므로 $를 그대로 쓰고 세 번째 칸으로 헤드를 옮기며 기계의 상태를 B라 둔다.
3. 세 번째 칸에서 기계의 상태는 B이고, 읽은 기호는 *이므로 *을 그대로 쓰고 세 번째 칸으로 헤드를 옮기며 기계의 상태를 C라 둔다.
4. 다시 두 번째 칸에서 기계의 상태는 C이고, 읽은 기호는 $이므로 *를 쓰고 세 번째 칸으로 헤드를 옮기며 기계의 상태를 C라 둔다.
5. 세 번째 칸에서 기계의 상태는 C이고, 읽은 기호는 *이므로 $를 쓰고 네 번째 칸으로 헤드를 옮기며 기계의 상태를 B라 둔다.
6. …
7. 최종적으로 아래 그림이 된다.

• 문제 예시

  임의의 이진수를 1 증가하는 것은 다음과 같이 튜링 머신으로 나타낼 수 있습니다.

  1. 초기화: 테이프에 이진수를 입력하고, 테이프 헤드는 이진수의 가장 오른쪽 끝을 가리키도록 합니다. 상태는 시작 상태로 설정합니다.
  2. 현재 읽은 심볼이 0이면, 1로 바꿉니다.
  3. 현재 읽은 심볼이 1이면, 0으로 바꾸고 테이프 헤드를 왼쪽으로 이동합니다.
  4. 테이프 헤드가 이진수의 가장 왼쪽을 가리키고 있는지 확인합니다. 가장 왼쪽이 아니라면 2번으로 돌아가서 다시 실행합니다.
  5. 테이프에 있는 이진수가 1로 시작하는지 확인합니다. 1로 시작하지 않으면 오류를 출력합니다.
  6. 모든 작업이 완료되면 종료합니다.

시험 대비

1. 튜링 머신의 개념 및 작동 방식: 튜링 머신이 무엇인지, 테이프와 테이프 헤드, 상태 레지스터와 규칙 레지스터 등의 개념, 튜링 머신이 어떻게 동작하는지 등에 대한 이해와 설명이 요구됩니다.
   • 튜링 머신: 알고리즘을 실행하는 수학적 모델
     1. 테이프 (Tape): 무한대의 저장 공간으로, 각 칸은 0 또는 1과 같은 심볼을 담을 수 있습니다.
     2. 테이프 헤드 (Tape Head): 테이프에서 현재 위치를 가리키는 역할을 합니다. 헤드가 가리키는 칸에 저장된 심볼을 읽거나 쓸 수 있습니다.
     3. 제어 유닛 (Control Unit): 튜링 머신의 동작을 제어합니다. 제어 유닛은 현재 상태를 나타내는 상태 레지스터와, 규칙 테이블을 참조하여 다음 동작을 결정하는 규칙 레지스터를 포함합니다.
     4. 규칙 테이블 (Rule Table): 현재 상태와 읽은 심볼에 대한 다음 상태, 쓸 심볼, 헤드를 이동시킬 방향 등을 결정합니다.
2. 튜링 머신으로 계산 가능한 문제: 튜링 머신이 어떤 종류의 계산 문제를 해결할 수 있는지, 튜링 머신으로 풀 수 있는 문제의 종류와 그 한계 등에 대한 이해가 필요합니다.
   • 어떤 컴퓨터나 계산기가 풀 수 있는 문제는 튜링 머신도 풀 수 있습니다.
   • 결정론적 문제(deterministic problem)
     • 두 수를 더하는 문제나 주어진 문자열이 회문인지 아닌지 판별하는 문제
   • 비결정론적 문제(non-deterministic problem)
     • 주어진 그래프에서 최단 경로를 찾는 문제나 주어진 불린 식이 성립하는지 아닌지 판별하는 문제
   • 비결정론적 문제중에서는 튜링 머신으로 못푸는것도 존재
3. 튜링 완전성: 튜링 완전성이 무엇인지, 어떤 종류의 계산 문제가 튜링 완전한지, 다른 계산 모델과의 관계 등에 대한 이해와 설명이 요구됩니다.
   • 튜링 완전성: 어떤 계산 모델이 튜링 머신과 동등한 계산 능력을 가진 것을 말합니다. 튜링 완전하지 않다 = 튜링 머신으로 해결이 불가능하다.
   • 대다수의 프로그래밍 언어는 튜링 완전성이다.
   • 유한상태기계(finite state machine)는 메모리가 무한하지 않아서 튜링 완전성이 떨어진다.
4. 컴퓨터 과학에서의 응용: 튜링 머신이 컴퓨터 과학 분야에서 어떻게 활용되는지, 오토마타, 언어 이론 등 다른 분야와의 관계 등에 대한 이해와 설명이 요구됩니다. 이건 안나올거 같은데…
   1. 오토마타 이론: 튜링 머신은 오토마타 이론의 기초가 되는 개념입니다. 튜링 머신을 이용해 구성된 오토마타들은 다양한 분야에서 사용되며, 예를 들어 프로그래밍 언어 컴파일러에서 사용되는 구문 분석기(parser) 등에서 활용됩니다.
   2. 계산 이론: 튜링 머신은 계산 이론의 핵심 개념입니다. 튜링 머신의 이론적인 구조를 통해 계산의 복잡도와 계산 가능성 등을 분석할 수 있습니다.
   3. 알고리즘 분석: 튜링 머신은 알고리즘 분석의 도구로도 활용됩니다. 예를 들어, 어떤 알고리즘이 튜링 머신의 형태로 구현될 수 있는지, 그리고 그 알고리즘의 수행 시간이나 공간 복잡도를 튜링 머신으로 분석할 수 있습니다.
   4. 인공지능: 튜링 머신은 인공지능 분야에서도 활용됩니다. 특히, 인공지능 분야에서 많이 사용되는 머신러닝 알고리즘은 대개 튜링 머신과 유사한 형태로 구성됩니다.
   5. 암호학: 튜링 머신은 암호학 분야에서도 사용됩니다. 예를 들어, 튜링 머신의 암호학적 응용으로는 RSA 알고리즘이 있습니다.