[인공지능] 튜링 머신 - 개요, 구성, 보편 튜링 머신

1. 개요

튜링 머신은 수학자 앨런 튜링이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계이며 오토마타의 일종이다. 튜링은 이 개념을 automatic에서 따온 a-machine이라고 불렀는데 튜링 사후에 창시자의 이름을 따 튜링 머신이라고 부르게 되었다.

2. 구성

튜링 머신은 아래와 같은 장치로 이루어진다:

• 테이프(Tape): 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있다.
• 헤드(Head): 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다. 또는 헤드는 고정되어 있고 테이프가 이동한다.
• 상태 기록기(State register): 현재 튜링 머신의 상태를 기록하고 있는 장치.
  • 개시 상태(Start state): 상태 기록기가 초기화된 상태를 의미한다.
  • 종료 상태(Halt state): 수행이 종료된 상태.
• 행동표(Action table, transition table of instructions): 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다.
  • 기호를 지우거나 고쳐 쓴다.
  • 헤드를 오른쪽, 왼쪽으로 한 칸 움직이거나 그 자리에 머문다.
  • 상태를 변경한다. 같은 상태에 머무를 수도 있다.

튜링 머신에서 종이 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 개수는 모두 유한해야 하며 서로 구분되어야 한다.

아래와 같은 개념을 일반화해 둔 것이다.

• '현재 상태가 1인데 기호 'A'를 읽었다면 'B'를 기록하고 정지.'
• '현재 상태가 1인데 기호 'B'를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경'
• '현재 상태가 2인데 기호 'C'를 읽었다면 오른쪽으로 한 칸 이동'

2.1. 보편 튜링 머신

Universal Turing Machine.

원래의 튜링 머신은 행동표에 적힌 규칙에 따라서 할 수 있는 일이 정해져 있다. 그런데 우리는 모든 일을 다 처리할 수 있는 기계를 원하고 그래서 보편 튜링 머신이라는 개념이 나왔다. 보편 튜링 머신은 하나의 튜링 머신이지만 다른 임의의 튜링 머신을 시뮬레이션할 수 있다. 이것은 행동표에 해당하는 내용을 테이프에 적어놓음으로 가능하다. 상태집합 Q와 행동표 R로 이루어진 튜링 머신 M이 있다고 하면, 우선 Q와 R을 테이프에 기록해두고 이후 실제로 M이 수행할 작업을 테이프에 기록한다. 보편 튜링 머신은 먼저 Q와 R을 읽어서 내부적으로 상태 전이 그래프를 구축한다. 이후 테이프를 읽으며 실제로 M이 수행해야 할 작업을 수행한다. 이런 과정을 통해 모든 튜링 머신을 흉내낼 수 있는 보편 튜링 머신을 상정할 수 있다. 즉, 행동표와 작업 내용을 테이프(메모리) 하나에 모두 저장할 수 있다. 이것을 바탕으로 만든 계산기계가 폰 노이만 구조 컴퓨터로, 프로그램 내장형 컴퓨터 개념의 시초가 되었다.

최초의 보편 튜링 머신은 콘라드 추제의 Z3이었다. 그러나 최초의 디지털 연산 컴퓨터로는 콜로서스가 그 자리를 차지[1]한다.

---

튜링 머신 - 나무위키 (namu.wiki)

목차	링크
1. 개요
2. 구성
2.1. 보편 튜링 머신
2.2. 다중 테이프 튜링 머신
2.3. 튜링 동치(Turing equivalence)
2.4. 튜링 완전성(Turing completeness)
3. 컴퓨터와 튜링 머신
4. 튜링 완전한 언어
4.1. 절차적 언어
4.2. 람다 대수(Lambda calculus)
5. 튜링 머신의 한계
6. 처치-튜링 명제
7. 관련 문서

 

---

인공지능/논란 - 나무위키 (namu.wiki)

목차	링크
1. 개요	* [인공지능] 인공지능 논란 - 개요, 기술적 실업, 기술적 특이점 (tistory.com) * [인공지능] 인공지능 논란 - 3. 기술적 특이점 (tistory.com) * [인공지능] 인공지능 논란 - 3. 기술적 특이점 - 이어서 (tistory.com) * [인공지능] 인공지능 논란 - 3. 기술적 특이점 - 이어서 2 (tistory.com)
2. 기술적 실업 - 기술적 실업 - 나무위키 (namu.wiki)
3. 기술점 특이점
3.1. 인공지능도 의식을 가질 수 있는가
4. 신뢰의 문제
5. 저작권, 초상권, 지적 재산권 문제
6. 빅브라더 사회 실현	[인공지능] 인공지능 논란 - 5. 저작권, 초상권, 지적 재산권 문제 6. 빅브라더 사회 실현 (tistory.com)
7. 인공지능에 대한 가해 성립 여부
8. 인공지능이 가져올 변화에 대한 낙관과 비관
8.1. 인공지능의 발전에 두려움을 가질 필요가 없다는 의견
8.2. 부정적 가능성에 대한 관심과 대처가 필요하다는 의견
8.3. 관련 기사
9. 관련 문서

 

---

인공지능 - 나무위키 (namu.wiki)

목차	링크
인공지능	https://somehow-a-programmer.tistory.com/221
1. 개요
2. 역사
2.1. 2022년 이후, 생성형 인공지능의 시대
3. 인공지능의 미래
3.1. 유토피아/디스토피아	https://somehow-a-programmer.tistory.com/225
4. 단계	https://somehow-a-programmer.tistory.com/226
5. 접근법 및 현황
5.1. 접근법	https://somehow-a-programmer.tistory.com/232
5.2. 연구 현황
5.3. 기술 개발 현황	https://somehow-a-programmer.tistory.com/235
5.4. 인프라	https://somehow-a-programmer.tistory.com/240
5.5. 장단점	https://somehow-a-programmer.tistory.com/244
5.6. 논란    번외)_튜링 머신 - 팔 내용 많음.. 번외의 번외 편으로 공부 ㄱ
5.7. 인공지능의 생명과 감정감별	https://somehow-a-programmer.tistory.com/247
5.7.1. 인공지능도 의식을 가질 수 있는가
6. 평가	https://somehow-a-programmer.tistory.com/252
7. 대중매체
8. 여담
9. 관련 문서
9.1. 관련 언어 목록