튜링 머신

인공지능을 판별하는 시험에 대한 내용은 튜링 테스트 문서 참고하십시오.

수학기초론 Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	다루는 대상과 주요 토픽
수리논리학	논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론	집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론	범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론	계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보		}}}}}}}}}

''' 이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	<colbgcolor=#a36> 이론
기본 대상	수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론	재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론	FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론	점근 표기법 · 튜링 기계^^{고전, 양자, 비결정론적, 병렬 임의접근 기계}^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론	데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론	프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초	정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현	배열^^벡터^ · 리스트^^{연결 리스트}^ · 셋(set)^^{레드-블랙 트리, B-트리}^ · 우선순위 큐^^{힙, 피보나치 힙}^
수학적 최적화	조합 최적화	외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
	볼록 최적화	내부점 방법 · 경사하강법
	선형계획법	심플렉스법
계산 수론 및 암호학	밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
	대칭키 암호화 방식	블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
	공개키 암호화 방식	공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학	볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^^{Fortune의 line-sweeping 알고리즘}^ · 범위 탐색^^{vp-tree, R-tree}^ · k-NN
그래프 이론	탐색^^{BFS, DFS, 다익스트라 알고리즘, A* 알고리즘}^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제^{대각선 논법} · 암달의 법칙 · P-NP 문제^미해결 · 콜라츠 추측^미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학			}}}}}}}}}

[[컴퓨터공학|컴퓨터 과학 & 공학

Computer Science & Engineering

]]

[ 펼치기 · 접기 ]

||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 || 수학( 해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학( 환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학( 형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||

하드웨어 구성	SoC · CPU · GPU( 그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술	기계어 · 어셈블리어 · C/ C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시( SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속
연구 및 기타	논리 회로( 보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{ 컴파일러( 어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩( 유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도( 최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리( 기계 번역 · 음성인식) · 버전 ( 버전 관리 시스템 · Git · GitHub)

	앨런 튜링 관련 문서
{{{#!wiki style="margin: 0 -10px -5px; min-height: 28px;" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -6px -1px -11px; word-break: keep-all;"		<colbgcolor=#000><colcolor=#fff> 연구 업적	<colcolor=#000,#fff> 튜링 머신 · 튜링 테스트 · 에니그마
행적 및 활동	생애
소속	케임브리지 대학교( 킹스 컬리지) · GC&CS · 프린스턴 대학교 · 맨체스터 대학교
관련 학자	클로드 섀넌 · 존 폰 노이만 · 알론조 처치
기타	튜링상 · 인공지능 · 유전학 · 이미테이션 게임(영화)

}}}}}}}}} ||

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. 튜링 머신 구현 예시8. 관련 문서

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]한다.

2.2. 다중 테이프 튜링 머신

Multitape Turing Machine.

헤드와 테이프가 여러개 달려 있는 튜링 머신. 기존의 튜링 머신에 비해 강력하고 폭넓은 작업을 해 줄 수 있으리라 예상하였으나, 헤드와 테이프를 몇 개 달아놓든 단일 테이프 튜링 머신과 동치라는 것이 증명되었다.

2.3. 튜링 동치(Turing equivalence)

만일 컴퓨터 P와 Q가 있을 때, P가 할 수 있는 일을 Q가 모두 흉내(simulate)낼 수 있고, Q가 할 수 있는 일을 모두 P가 흉내낼 수 있다면 두 컴퓨터는 튜링 동치이다.

2.4. 튜링 완전성(Turing completeness)

어떤 컴퓨터 P가 있어서 그 컴퓨터와 보편 튜링 머신이 튜링 동치라면 P는 튜링 완전(Turing complete)하다. 정확히 말하면 P가 보편 튜링 머신을 시뮬레이션 할 수 있으면 충분하다. 보편 튜링 머신은 모든 튜링 머신을 흉내낼 수 있다고 생각되므로 자동으로 동치가 된다.

3. 컴퓨터와 튜링 머신

현대의 폰 노이만 구조로 된 컴퓨터는 모두 보편 튜링 머신 이론에 바탕을 두고 있다. 따라서 보편 튜링 머신은 현대의 모든 컴퓨터의 동작을 포함하는 큰 집합이다. 코드 메모리와 데이터 메모리가 분리되어있는 하버드 구조는 테이프를 두 개 달아놓은 튜링 머신이라고 생각할 수 있으니 보편 튜링 머신은 하버드 구조의 컴퓨터도 완벽하게 흉내낼 수 있다. 이로 인하여 컴퓨터의 작업을 이론적으로 모델링할 때는 모두 튜링 머신 이론을 활용한다.

다만 현실의 컴퓨터와 튜링 머신에 약간의 차이점은 있는데, 튜링 머신은 메모리 임의 접근을 상정하지 않고 있다. 다시 말해 테이프의 아무 위치나 원하면 바로 접근할 수는 없다. 이진 탐색 같은 알고리즘의 시간복잡도는 임의 접근이 가능하다면 O(lgN) 시간 안에 끝나지만 튜링 머신에서는 훨씬 더 느린 O(N)의 속도를 보인다. 물론 이것은 접근 방식의 차이이지 튜링 머신도 유한한 행동 안에 그 접근을 똑같이 따라할 수 있으므로 기능적으론 동일하다.

현실의 모든 컴퓨터는 엄밀히 따지면 '튜링 완전'하지 않은데, 그 이유는 기억장치가 유한하기 때문이다. 튜링 머신의 테이프는 무한한 길이를 가져야 하는데 현실의 컴퓨터는 무한한 데이터를 보관할 수 없다. 다만 그렇다고 해서 컴퓨터들이 보편 튜링 머신을 무시한 것은 아니다. 이상 기체는 현실에 없지만 이를 기반으로 한 이상 기체 법칙은 충분히 활용되는 것처럼 현실의 컴퓨터도 튜링 머신을 기반으로 설계되었기 때문에 유한한 작업을 수행함에 있어 그 이론을 충실히 따르고 있다.

따라서 기억장치가 유한하지만 튜링 완전성을 따르고 있다는 것을 일컬어 '느슨한 튜링 완전성(Loose Turing Completeness)'이라고 한다. 대부분의 컴퓨터는 '느슨한 튜링 완전'이다. 그렇기 때문에 어떤 컴퓨터가 할 수 있는 모든 일은 '충분한' 시간과 메모리만 주어진다면 다른 어떤 간단한 컴퓨터로도 할 수 있다. 여러분의 컴퓨터는 슈퍼컴퓨터와 다르지 않다. 다만 그보다 느리고 용량이 작을 뿐이다.

인터넷을 보면 마인크래프트 레드스톤과 같은 게임으로 '컴퓨터'를 구현했다고 하는 글이나 영상을 종종 볼 수 있다. 이는 해당 게임들의 인게임 요소를 가지고 튜링 완전성을 따르는 장치를 구현한 것이다. 따라서 매우 비효율적이지만 컴퓨터와 마찬가지로 '느슨한 튜링 완전'이기 때문에 컴퓨터가 할 수 있는 일을 똑같이 할 수 있다. 마인크래프트로 계산기를 구현했다거나 하는 것들은 다 이런 뜻이다. 예시들은 아래 문단 참조.

4. 튜링 완전한 언어

어떤 언어의 튜링 완전성을 보이려면, 튜링 머신과 동치인, 이하 서술되는 다른 시스템과 동치임을 보이면 된다.

4.1. 절차적 언어

다음 두 가지 기능을 가지고 있다면 (느슨하게) 튜링 완전하다.

조건 분기문이 있다. if (...) then goto (...). 또는 branch if zero 등. for, while 등의 루프문은 모두 조건 분기문으로 바꿔 쓸 수 있다.
임의 위치의 메모리 값을 바꿀 수 있다.

C, 파스칼 등 널리 사용되는 절차적 언어는 대부분 위 두 조건을 충족하기에 튜링 완전하다. 난해한 프로그래밍 언어에서 소개되는 대부분의 절차적 언어 역시 위 두 조건을 충족하기에 튜링 완전하다. C++의 템플릿 메타 프로그래밍도 컴파일 타임 튜링 완전하다.

' HTML은 프로그래밍 언어가 아니다\'라는 말은 여기서 나온 것이다. HTML은 조건 분기도 없으며 메모리를 바꾸는 것도 불가능하기 때문에 튜링 완전하지 않기 때문이다. 프로그래밍 언어/종류 문서를 보면 알겠지만 이런 언어들은 ' 마크업 언어'라고 해서 따로 분류한다. 다만 HTML5와 CSS3의 조합은 튜링 완전하다고 증명된 110 세포자동자를 흉내낼 수 있으므로 튜링완전하다.

실용적인 사례는 아니지만 좀 극단적인 예 하나는 단일 인스트럭션 컴퓨터(One Instruction Set Computer)이다. 영문 위키백과의 항목을 보면 '빼기 연산을 하고 결과가 0 이하이면 점프(SUbtract and Branch if Less than or EQual to zero = SUBLEQ)'하는 연산 하나만으로 임의 위치의 메모리 값 바꾸기, 조건 분기하기를 구현하고 있다. 이 경우 역시 위 두 조건을 만족하니 튜링 완전하다.

4.2. 람다대수(lambda calculus)

람다대수는 알론조 처치에 의해 튜링 기계보다 먼저 제안된 계산 모델이며 람다대수로 할 수 있는 모든 계산은 튜링 기계로도 가능하고 그 역도 성립한다는 것이 증명되었다. 람다대수와 동치인 언어 역시 튜링 완전하다. 프로그래밍 언어에서는 튜링 기계보다 람다대수를 더 널리 이용한다.

5. 튜링 머신의 한계

튜링 머신은 우리가 상상할 수 있는 거의 모든 계산을 할 수 있다. 다만 모든 것을 할 수 있지는 않다. 예를 들어 어떤 튜링 머신이 주어진 입력에 대해 유한 시간 내에 정지하는지를 묻는 문제는 튜링 머신으로 답할 수 없다. 이것이 정지 문제이다.

이것을 비롯하여 수많은 문제들이 튜링 머신으로 할 수 없음이 증명되었다. 대부분의 증명 방식은 문제를 정지 문제와 동치인 문제로 변형하는 형식이다.

6. 처치-튜링 명제

Church-Turing thesis.
알고리즘으로 할 수 있는 모든 일이 튜링 기계로 실행될 수 있다는 것이다. 현재까지 알려진 모든 알고리즘들은 튜링 기계로 실행될 수 있다고 추측된다. 그러나 알고리즘의 정의가 명확하지 않으므로 이 명제가 증명되기는 어렵다. 양자컴퓨터 또한 이것을 벗어나지 않는다. 지금까지 알려진 모든 양자컴퓨터는 튜링 기계에 의해 시뮬레이션될 수 있고 역시나 처치-튜링 명제가 성립한다. 대부분의 학자들은 처치-튜링 명제가 참일 것이라고 여기고 있다. 다시 말하자면 위에서 말한 튜링 머신의 한계들은 어떤 방법으로도 해결 불가능할 것이라고 생각되고 있다.

처치-튜링 명제는 사람의 뇌 또한 하나의 컴퓨터에 지나지 않을 수 있음을 암시하고 있다. 그런데 오히려 로저 펜로즈 등은 인간의 뇌가 컴퓨터와 다른 능력을 지녔으며 그렇기 때문에 처치-튜링 명제가 완전하지 않다고 여긴다. 펜로즈는 불완전성 정리에 의해 튜링 기계, 다시 말해 모든 기계적 컴퓨터에는 한계가 존재하는데 사람의 뇌는 그렇지 않다는 것이다. 그렇기 때문에 알려지지 않은 어떤 새로운 양자역학의 개선에 의해 튜링 기계보다 뛰어난 능력을 가질 수 있다는 것이다. 그러나 철학적으로 문제가 많은 주장이기에 주류 학계에서는 진지하게 받아들여지지 않는다.

더 강한 버전으로 Church–Turing–Deutsch principle이란 것이 존재한다. 알고리즘을 넘어서 아예 모든 물리적 과정이 튜링 기계로 시뮬레이션될 수 있다는 것이다. 다만 이 때는 시뮬레이션의 정의도 명확치 않을뿐더러 처치-튜링 명제와 마찬가지로 증명되기는 어려운 성질의 것이다.

1936년 수리논리학자인 알론조 처치가 람다대수의 관점에서 먼저 제안했고 이는 튜링의 방법과 차이가 존재하기 때문에 수리논리학자들은 처치의 명제를 튜링의 명제와 구분하기도 한다. 처치의 명제는 결정가능한 모든 계산가능한 함수가 재귀적이라는 것이다. 같은 해인 1936년에 앨런 튜링이 튜링 머신을 통해 별개의 방향으로 이를 이상화시켜 나타난 개념이 처치-튜링 명제이다.

7. 튜링 머신 구현 예시

게임

논리 회로 기능

마인크래프트: 레드스톤 회로를 통해 각종 계산 장치들을 만들 수 있다.
테라리아: 2진법 10진법 변환기 등을 만들 수 있다.

기타 시스템 활용

Baba Is You: IS를 계속 아래로 움직여 Rule 110을 구현할 수 있다.
롤러코스터 타이쿤: OpenRCT2의 겹쳐짓기 모드를 통해 롤러코스터로 계산기를 구현할 수 있다.
매직 더 개더링: 관련 논문의 저자들은 60장의 적법한 레가시 포맷 덱으로 튜링 머신을 시뮬레이션하고 승리 조건을 정지 문제와 동치시킴으로서 최적의 플레이를 계산하는 알고리즘이 존재하지 않는다는 것을 증명했다.
시티즈: 스카이라인: 급수탑과 풍력발전기 등을 통해 폐수 계산기를 만들 수 있다.

소프트웨어

Microsoft Excel: LAMBDA를 통해 타언어로 만든 커스텀 수식 없이 엑셀 수식으로만 튜링 완전하게 되었다.

컴퓨터 언어

CSS: 상태 선택자 :checked와 조합자 +를 사용해 Rule 110을 구현할 수 있어 튜링 완전하다.
TypeScript의 타입 시스템: 재귀적인 타입 정의를 통해 SmallFuck과 유사한 방식으로 작동시킬 수 있다. #

기타

구슬: 구슬의 움직임을 통해 Rule 110을 구현할 수 있다.
종이접기: 2023년 종이접기로 튜링 완전한 장치를 구현할 수 있다는 것이 증명되었다. # 해당 논문에 따라 OR, AND, NOT 게이트를 종이접기로 만든 영상 참조.

8. 관련 문서

앨런 튜링
오토마타
폰 노이만 구조
알고리즘
프로그래밍 언어
해석기관 - 튜링 머신의 개념이 등장하기 전에 구상된 기계식 연산장치로, 튜링 머신의 조건을 만족하여 컴퓨터의 역할을 수행할 수 있다.
정지 문제
바쁜 비버
컴퓨터 관련 정보

[1] 원래 보편 튜링 머신이 아니지만, 10대를 모아 클러스터링 하면 보편 튜링 머신이 된다. - DOI 10.1007/s11047-010-9225-x