튜링 머신

튜링 머신 turing machin

- 앨런 튜링이 소개한 실제 기계가 아닌 추상적 수학 개념의 오토 마타

- 임시 저장소가 테이프인 오토마타 

 -> 테이프는 셀로 나눠짐. 각 셀은 한개의 심볼을 저장

 -> 테이프와 관련하여 읽기 쓰기 헤드가 있음. 왼쪽/오른쪽으로 이동하여 하나의 심볼을 읽고 쓸수 있음

 

 

튜링 머신과 간단한 컴퓨터 비교

- 간단한 컴퓨터 : 유한 메모리를 갖는 프로세서 유닛을 가짐 -> 컴퓨터가 수행 가능한 명령어가 극히 제한됨

- 튜링 머신 : 테이프에 무한한 양의 보조 저장소를 가짐

 

 

튜링 머신의 기원

- 힐베르트의 열한번째 문제 : 모든 수학 문제를 풀 수 있는 알고리즘을 찾아라 -> 그런 알고리즘(기계가) 존재할수있는가?

- 기계적 프로그램의 정의

 -> 튜링은 기계 동작을 기본적인 식으로 나누어 정형화하여 기계라는 개념을 수식으로 표현하려고함

 -> 튜링은 사람의 뇌도 하나의 기계로 간주

 => 수학 문제를 푸는 수학자의 행동이 기계적 프로그램으로 묘사가능

 

 

튜링 기계와 형식 체계

- 튜링 기계는 알고리즘 or 프로그램이라 불러도 됨

- 우리 주위 모든 컴퓨터들은 튜링기계라 볼 수 있음

- 튜링 기계화 형식 체계는 다음음의 일대일 대응일 이룸

튜링머신	형식체계
입력	공리
프로그램	추론 규칙
출력	정리

 

 

 

 

* 튜링 머신과 재귀 하수, 람다 계산법, 포스트 시스템 등 모두 같은 개념