'지금까지 만들어지지 않은 가장 중요한 기계', 앨런 튜링과 튜링 기계

계산은 우리 대부분이 직관적으로 이해하는 친숙한 개념입니다. 함수 f(x) = x + 3을 예로 들어 보겠습니다. x가 3일 때 f(3) = 3 + 3입니다. 대답은 6입니다. 매우 간단합니다. 분명히 이 함수는 계산 가능합니다. 그러나 일부 기능은 그렇게 간단하지 않으며 계산 가능 여부를 결정하는 것이 쉽지 않습니다. 즉, 최종 답변으로 이어지지 않을 수도 있습니다.

1928년 독일 수학자 David Hilbert와 Wilhelm Ackermann은 Entscheidungsproblem("결정 문제")이라는 문제를 제안했습니다. 시간이 지남에 따라 그들이 묻는 질문은 계산 가능성에 대한 공식적인 정의로 이어질 것입니다. 이 정의는 수학자들이 수많은 새로운 질문에 대답하고 이론적 컴퓨터 과학의 기초를 마련할 수 있게 해줍니다.

23세의 대학원생인 Alan Turing은 1936년에 컴퓨팅의 개념을 공식화했을 뿐만 아니라 수학적 기본 질문이 발명의 지식 기반을 만들었다는 중요한 논문을 썼습니다. 전자 컴퓨터의. Turing의 위대한 비전은 추상적 기계의 형태로 컴퓨팅 문제에 대한 구체적인 답을 제공하는 것이었고, 나중에 그의 PhD 지도교수인 Alonzo Church가 이를 Turing 기계라고 명명했습니다.

튜링 기계는 물리적으로 유형의 장치로 존재할 수 없기 때문에 추상적입니다. 오히려 이는 계산의 개념적 모델입니다. 이 기계가 함수를 계산할 수 있으면 함수도 계산 가능합니다.

Alan Turing은 1936년에 Turing 기계를 발명했을 때 현대 컴퓨팅도 창조했습니다.

Alan Turing and his Turing Machine

작동 방식은 다음과 같습니다. Turing 기계는 규칙표에 따라 무한히 긴 테이프의 기호를 읽고 변경할 수 있습니다. 테이프는 "셀"로 구성되며 각 셀은 하나의 기호만 저장할 수 있습니다. 튜링 기계는 테이프 헤드를 사용하여 셀의 내용을 읽고 다시 씁니다. 규칙 테이블의 각 규칙은 현재 상태와 읽고 있는 기호를 기반으로 Turing 기계가 수행해야 하는 작업을 결정합니다. 튜링 기계는 정지 위치에 따라 최종 상태("수락 상태" 또는 "거부 상태")에 들어가 입력을 수락할지 거부할지 결정할 수 있습니다. 또는 Turing 기계가 무한 루프에 빠져 테이프 읽기를 멈추지 않습니다.

튜링 기계를 이해하는 가장 좋은 방법은 이와 같은 간단한 예를 생각해 보는 것입니다. 주어진 입력이 숫자 0인지 여부를 알려주도록 튜링 기계가 설계되었다고 가정해 보겠습니다. 공백 기호(#)와 함께 숫자 0001을 입력합니다. 이는 "#0001#"이 테이프의 관련 부분임을 의미합니다.

튜링 기계는 초기 상태에서 시작하여 이를 q0이라고 부르며, 테이프의 가장 왼쪽 셀을 읽고 빈 영역을 찾습니다. 원칙적으로 상태 q0에서 부호가 #이면 그대로 두고 한 셀을 오른쪽으로 이동하여 기계 상태를 q1로 변경합니다. 이 단계 후에 기계는 상태 q1에 있고 헤드는 두 번째 기호 0을 읽습니다.

이제 이러한 조건에 적용되는 규칙을 찾습니다. "상태 q1을 유지하고 머리를 오른쪽으로 한 셀 이동"이라는 규칙을 찾았습니다. 이로 인해 우리는 동일한 위치에 있게 되므로(상태 q1에서 판독값은 여전히 ​​0임) 머리가 나올 때까지 계속 오른쪽으로 이동합니다. 마지막으로 다른 숫자 1을 읽습니다.

규칙 테이블을 다시 참조한 결과 "1이 발견되면 거부 상태인 q2로 전환됩니다."라는 새로운 규칙을 발견했습니다. Turing 기계는 실행을 멈추고 원래 질문인 "0001이 0인가요?"에 대답했습니다. ?" "아니요"라고 대답하세요.

반대로, 입력이 "#0000#"이면 Turing 기계는 모든 0 다음에 #을 만나게 됩니다. 규칙 테이블을 참조하면 이것이 기계가 "수락" 상태인 q3 상태에 들어간다는 것을 의미하는 규칙을 찾습니다. 이제 기계는 "'0000'이 0입니까?"라는 질문에 "예"라고 대답합니다.

Alan Turing은 계산, 알고리즘 및 Turing 기계를 정의하는 데 도움을 주었습니다.

추상 기계로 판단적 질문에 답하기

튜링은 자신의 추상 기계를 사용하여 Entscheidungs ​​​​문제에 답하기 위한 계산 모델을 구축했습니다. 이 문제는 공식적으로 다음과 같이 묻습니다. 일련의 수학적 공리가 주어지면 기계적 과정이 존재하는지 여부( 즉, 주어진 진술이 참인지 항상 결정할 수 있는 일련의 명령, 오늘날 우리는 이를 알고리즘이라고 부릅니다.

특정 체스 게임에서 말의 위치가 가능한지 여부를 알려주는 알고리즘을 찾고 싶다고 가정해 보겠습니다. 그 안에서 공리는 체스의 합리적인 움직임을 지배하는 규칙입니다. 유한한 순서의 단계별 프로세스를 따라가면 거기에 도달할 수 있을까요? 일부 체스 위치는 분석하는 데 우리 수명보다 오래 걸릴 수 있지만 알고리즘은 가능한 모든 위치를 생성하고 이를 입력과 하나씩 비교할 수 있습니다. 이러한 알고리즘은 체스 게임에 존재합니다. 그러므로 우리는 체스를 "결정 가능"하다고 말합니다.

그러나 1936년 미국 수학자 처치(Church)와 튜링(Turing)은 "엔체이둥 문제의 모든 예를 해결할 수 있는 일반적인 방법은 없다"는 것을 증명하기 위해 서로 다른 방법을 사용했습니다. 예를 들어 존 콘웨이(John Conway)의 게임 오브 게임(Game of Game)과 같은 일부 게임도 있습니다. 인생은 결정불가능합니다. 어떤 알고리즘도 초기 패턴에서 특정 패턴이 나타날지 여부를 결정할 수 없습니다.

Turing은 필요한 작업을 수행할 수 있는 알고리즘이 있으면 함수를 계산할 수 있음을 보여주었습니다. 동시에 그는 알고리즘이 튜링 기계에 의해 정의될 수 있는 프로세스임을 보여주었습니다. 따라서 계산 가능한 함수는 튜링 기계로 계산할 수 있는 함수입니다. 이것은 계산 가능성을 정의하는 우회적인 방법처럼 보이지만 우리가 가진 최선의 방법입니다.

MIT의 이론적 컴퓨터 과학자인 Michael Sipser는 다음과 같이 말했습니다. "그것을 다른 방식으로 정의할 수 있다는 것은 아닙니다. 사람들은 일반적으로 Church-Turing 논문이 알고리즘의 비공식적 개념이 무엇인지 제안한다는 데 동의한다고 생각합니다. 어떤 합리적인 계산 모델이라도 가능합니다. 다른 수학자들은 표면적으로는 다르지만 실제로는 동일한 여러 가지 계산 모델을 제안했습니다. 즉, Turing 기계가 수행할 수 있는 모든 계산을 수행할 수 있고 그 반대의 경우도 마찬가지입니다.

철학자, 논리학자, 수학자 Kurt Gödel이 수학이 불완전하다는 것을 보여준 지 불과 몇 년 후, Church와 Turing도 수학의 특정 문제가 이 워크시트로 해결될 수 없다는 것을 보여주었습니다. 알고리즘이 아무리 복잡하더라도 대답이 '예'인지 '아니요'인지 알려줄 수는 없습니다. 두 사건 모두 수학이 간단하고 이상적인 답을 제공해주기를 바랐던 힐베르트에게는 엄청난 타격이었습니다. 그러나 그것은 나쁘지 않습니다. Entscheidungs ​​문제에 대한 일반적인 해결책이 있다면 수학의 모든 문제가 간단한 기계 계산으로 축소될 수 있다는 의미입니다.

보편적이고 확률론적인 튜링 머신

이러한 근본적인 질문에 답하는 것 외에도 튜링 머신은 유니버설 튜링 머신이라는 변형을 통해 현대 컴퓨터의 개발에 직접적인 영향을 미쳤습니다. 이는 다른 Turing 기계의 입력을 시뮬레이션할 수 있는 특별한 Turing 기계입니다. 이는 다른 Turing 기계의 설명(및 규칙 및 입력 테이프)을 읽고 자체 입력 테이프에서 동작을 시뮬레이션하여 시뮬레이션된 기계와 동일한 출력을 생성할 수 있습니다. 이는 오늘날의 컴퓨터가 모든 프로그램을 읽고 실행할 수 있는 것과 같습니다.

1945년 헝가리계 미국인 수학자, 컴퓨터 과학자, 물리학자인 존 폰 노이만(John von Neumann)은 컴퓨터 아키텍처, 즉 보편적인 튜링 기계의 개념을 실제 기계로 바꾸는 폰 노이만 아키텍처를 제안했습니다.

프린스턴 대학교 이론 컴퓨터 과학자 Sanjeev Arora는 이 개념을 가르칠 때 더 넓은 철학적 그림을 강조합니다. 그는 "보편성에는 두 가지 개념이 있는데, 하나는 다른 튜링 기계를 실행할 수 있다는 것이고, 다른 하나는 우주에서 생각해내는 모든 계산을 실행할 수 있다는 것"이라고 말했다. 모든 물리적 프로세스는 알고리즘을 사용하여 모델링하거나 시뮬레이션할 수 있으며, 알고리즘은 Turing 기계로 시뮬레이션할 수 있습니다.

또 다른 주목할 만하고 점점 더 유용해지는 변형은 확률적 튜링 머신입니다. 각 입력에 대해 잘 정의된 응답을 갖는 기존 튜링 머신과 달리 확률적 튜링 머신은 확률을 기반으로 여러 응답을 할 수 있습니다. 이는 서로 다른 시점에 동일한 입력에 대해 서로 다른 결과를 생성할 수 있음을 의미합니다. 또한 놀랍게도 일부 문제의 경우 이 확률적 전략이 순전히 결정론적 접근 방식보다 더 잘 작동합니다. 확률론적 튜링 기계의 개념은 최적화 및 기계 학습과 같은 분야에서 매우 유용한 것으로 입증되었습니다.

이 추상 기계는 아마도 근본적인 질문을 하는 것이 과학자가 할 수 있는 가장 유용한 일 중 하나일 수 있다는 최고의 증거일 것입니다.

위 내용은 '지금까지 만들어지지 않은 가장 중요한 기계', 앨런 튜링과 튜링 기계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!