기록

튜링머신(Turing Machine)

튜링 머신은 앨런 튜링이 1936년에 제안한 이론적인 기계이다.

수학자 앨런 튜링은 힐버트 프로젝트의 목표에 도전하기 위해 튜링 머신 개념을 도입했다. 힐버트 프로젝트는 모든 수학적 명제를 증명해주는 만능 기계를 만들려는 시도였으나, 튜링은 이러한 프로젝트의 목표가 불가능하다는 것을 증명하기 위해 튜링 머신을 사용했다.

이러한 배경으로 제안된 튜링 머신은 컴퓨터 과학의 기초가 되는 개념이 되면서 컴퓨터가 수행할 수 있는 모든 계산 작업을 수행할 수 있으며, 이를 통해 컴퓨터 과학에서 다양한 계산 문제를 이해할 수 있게된다.

튜링 완전성(Turing Completeness)

컴퓨터 과학에서 중요한 개념으로, 계산 이론의 관점에서 특정 시스템이 모든 튜링 머신의 계산 수행 능력을 말하며 튜링 완전성은 컴퓨터 시스템의 계산 능력을 평가하는 기준이 된다.

튜링 완전한 시스템은 두 가지 기본 요소가 있다.

1. 기계의 상태를 나타낼 수 있는 유한한 수의 상태

2. 무한한 길이의 메모리를 사용

튜링 완전한 시스템은 모든 계산 문제를 해결할 수 있는 이론적인 기계로 볼 수 있으며 이를 통해 현대의 대부분의 프로그래밍 언어와 컴퓨터 아키텍처는 튜링 완전하다고 간주되고 이를 통해서 다양한 시스템 간의 계산 능력을 비교할 수 있다.

튜링 완전성을 갖춘 시스템은 어떤 알고리즘도 구현이 가능하며 이론적으로는 다른 튜링 완전한 시스템과 동일한 계산 능력을 가진다. 하지만 언제까지나 튜링 완전성은 이론적인 기준일 뿐 실제 성능을 반영하지 않기 때문에 실제로는 하드웨어 성능, 메모리 제한 등의 제약 때문에 모든 시스템이 동일한 성능을 내지는 않는다.

작동 방식

튜링머신은 무한히 긴 테이프가 있고 이 테이프는 일정한 크기로 나누어져 있으며 이를 셀이라고 부른다. 이 셀에는 기호가 기록되어있고 테이프를 따라 움직이는 헤더에 의해서 기록이 바뀔 수 있다. 튜링 머신의 상태는 상태 레지스터에 저장되고 이 상태에 대 따른 동작은 액션 테이블에 의해서 결정된다.

액션 테이블에 작성되는 동작은 테이프에 기호를 읽거나 새로 기록하고, 헤더를 왼쪽 또는 오른쪽으로 이동 그리고 정지의 기능을한다. 만약 액션 테이블에서 특정기호를 읽을 때 까지 헤더를 이동시키고 해당 기호를 읽었을 때 새로 기록을 하거나 또는 다른 동작을 수행시키는 등의 방식으로 모든 계산을 처리할 수 있는 기계로 동작하게 된다. 

한계

튜링 머신에는 계산할 수 없는 문제들이 존재한다.

튜링 머신은 이론적인 개념이기 때문에 현실에 존재할 수 없는 무한한 길이의 테이프와 무한한 시간을 가정으로한다. 따라서 유한한 메모리와 제한된 시간을 가지는 실제 컴퓨터에서는 동일한 계산 능력을 가질 수 없다,

그리고 또 다른 한계의 대표적인 예로는 튜링의 정지 문제(Halting Problem)가 있다. 이 문제는 어떤 튜링 머신이 특정 입력에 대해 정지할지 즉, 계산이 완료되어 결과를 출력하고 종료할것인지 또는 무한 루프에 빠져 계속 실행할지를 결정하는 문제이다. 튜링은 이 문제에 대한 알고리즘이 존재하지 않음을 증명했는데 이는 어떤 일반적인 알고리즘이나 프로그램이 입력과 조합에 대해 항상 올바른 정지 여부를 결정할 수 없음을 의미한다. 튜링은 이러한 튜링 머신이 정지문제에 대해서 해결할 수 없다는 점을 통해서 힐버트의 프로젝트를 반증 했다.

정지 문제의 불가능성은 튜링 머신과 같은 계산 모델의 한계를 보여주며, 컴퓨터 과학의 여러 분야에서 중요한 영향을 미친다. 예를 들어 프로그램의 정확성, 최적화 또는 자동 버그 찾기 등의 분야에서 이론적한계를 인식하고 이에 대한 해결책을 찾는데 도움이 된다.

정지 문제의 증명은 컴퓨터 과학과 수학에서 근본적인 한계를 보여주며, 계산 가능성 이론의 발전에 큰 영향을 미쳤다. 또한, 이 결과는 계산의 본질과 한계에 대한 연구를 촉진시키며 컴퓨터 과학의 핵심 개념으로 자리잡게 되었다.