오토마타, 튜링머신의 정의

수학자 튜링은 인간이 의식적으로 하는 정보 처리인 사고과정을 연구하여, 그 원리를 규명하려 하였다. 그는 순서에 의해 계산이나 논리조작을 행하는 알고리즘에 착안하여 이를 실행하는 장치로써 튜링 머신이라는 가공의 기계를 고안하였다. 그 결과 만능 튜링 머신이라는 것이 있고, 어떤 알고리즘도 이 기계를 사용하여 실행할 수 있음을 보였다. 현재의 용어로 표현하면 프로그램과 데이터를 기계에 주면 어떤 알고리즘도 실행 가능 하다는 것이다. 이처럼 튜링머신에 의한 직렬방식 기계 계산의 만능성을 보여줌과 동시에, 튜링은 그 한계도 명확히 했다. 즉, 함수 중에는 튜링머신으로 계산 불가능한 함수, 알고리즘으로는 풀 수 없는 문제가 있음을 보였다. 튜링머신인 컴퓨터는 1940년대 전자기술을 사용하여 기술적으로 실현되었다. 그러나 정보원리는 그 이전에 명확히 정립되어 있었다. 직렬 정보처리의 기초이론위에 알고리즘 이론, 언어이론, 데이터베이스의 이론등을 포함하는 컴퓨터과학이 탄생하였고, 그 위에 추가된 것이 인공지능이다.

튜링머신은 1936년에 Alan M. Turing이 고안한 추상적 기기로서 이는 매우 단조로우면서도 충분한 기억장소와 처리시간이 주어진다면, 모든 문제를 해결할 수 있는 알고리즘이 주어지는 한, 문제를 일반적으로 처리할 수 있는 도구로 사용할 수 있음을 일찍부터 인정받고 있다. 이것은 곧 일반목적에 사용될 수 있는 범용 컴퓨터의 이론적 원형(prototype)으로 정의될
수 있음을 의미한다.

따라서 튜링머신 은 범용 컴퓨터의 이론적인 시조로서 컴퓨터의 제반분야에 영향을 미치었고, 기계어가 아닌 프로그래밍 언어의 사용에 대한 기본생각을 제공하게 되었으며, 프로그램의 내장방식(stored program)이 가능해졌으며, 계산에 있어서 재귀적 함수(recursive function)를 제공하여 효율적인 계산기능을 표현할 수 있게 했으며, 이진 코드(binary code)의 사용을 실현케 하였다.