도령, 정체 문제와 디지털 시대의 서광

2000여 년 동안 위대한 엔지니어, 수학자, 과학자.고대의 안티키슬라 메커니즘에서 빅토리아 시대의 차이 엔진까지.1930년대, 40년대, 50년대에 일련의 활동이 우리를 시뮬레이션 시대에서 디지털 시대로 이끌었다.
1930년부터 1960년까지 이 시기는 역사의 경계선으로 볼 수 있다.30년의 역사는 2000여 년의 인류 역사를 전복시켰다.그것은 트랜지스터를 기반으로 한 디지털 컴퓨터의 발전에서 시작되었다.세계가 철저히 바뀌었다. 이 거대한 변화에 책임이 있다고 여겨지는 사람 중 한 명Alan Turing이다.

1936년 툴링은'계산 가능한 숫자에 관해 Entscheidungsproblem에 적용하는 것'이라는 제목의 논문을 발표했다. 이 논문은 다비드 힐버트와 윌리엄 아크만Decision Problem의 관점을 반박했다. 이것은 모든 문제가 판정할 수 있는지 물어보는 도전이다. 다시 말하면 진짜인지 가짜인지 증명할 수 있다. 메라니 미첼 교수가 묘사한 바와 같다.

Is there always a definite procedute that can decide whether or not a statement is true?

이 주장을 반박하기 위해 도령은 이론 디지털 컴퓨터로부터 시작하여 지금은 aTuring Machine라고 부른다.이 컴퓨터는 0, 1, 공백을 포함하는 무한 길이의 테이프에서 실행된다.읽기 및 쓰기 헤드는 테이프에서 입력을 읽고, 일부 규칙에 따라 프로그램은 출력을 테이프로 다시 쓴 다음 헤드를 정지하거나 이동하고 중복합니다.
모든 문제는 0과 1 (이진 코드라고도 함) 으로 인코딩한 다음, 읽는 0과 1에 따라 간단한 규칙을 따를 수 있다.가장 간단한 형식에서 인간은 테이프에서 0과 1을 읽고 규칙을 따를 수 있다original thought.비록 효율이 낮지만, 이 시스템은 계산 가능한 모든 문제를 계산하는 데 쓸 수 있다.
그러나 모든 문제가 계산할 수 있는 것이 아니라는 것을 증명하고 의사결정 문제를 반박하기 위해 도령은'모순증명'이라는 기술을 사용했다.그는 먼저 입력한 프로그램이 영구적으로 정지되거나 실행될지 계산할 수 있는 도령기를 만들 수 있을 것이라고 주장했다.그리고 나서 그는 이 기계가 갈등을 초래할 수 있기 때문에 존재할 수 없다는 것을 증명할 것이다.
도령이 언급한 이 생각은 나중에 Halting Problem라고 불렸다.오늘날 소프트웨어 개발자들은 이를 무한순환이라고 하는데, 이것은 많은 사람들이 순환이나 귀속 함수를 작성할 때 겪는 문제이다.다음은 C++에서 무한 순환하는 예를 볼 수 있습니다.while () '프로그램'은true를 입력하여 hello를 컨트롤러에 영원히 출력합니다.

#include <iostream>
using namespace std;

int main() {
  while (true) {
    cout << "hello" << endl;
  }
}

도령의 정지 문제 패러다임은 무한 순환 검사 기기를 만들면 버전을 만들 수 있으며, 그 기기가 자신에서 실행될 때 기계가 정확하고 잘못된 상태에 처하게 된다는 것을 보여 준다.이 모순은 무한순환 검측기를 건설하는 것은 불가능하다는 것을 보여준다.나는 정지 문제를 상세하게 묘사하기 위해 다른 문장이 필요하다. 지금 너는 단지 나의 말을 믿기만 하면 된다.
미첼의 말대로 이것은 수학과 컴퓨터에 있어서 모두 창의적인 일이다.

[Turing] rigorously defined the notion of “definite procedure.” Second, his definition, in the form of Turing machines, laid the groundwork for the invention of electronic programmable computers. Third, he showed what few people ever expected: there are limits to what can be computed.

도영기는 나중에 Turing Completeness의 개념을 제기하여 현대 컴퓨터와 프로그래밍 언어의 기준이 되었다.도영기는 간단한 기계나 프로그램으로 어떤 도영기의 행동도 모의할 수 있다.기본적으로, 이것은 그것이 모든 계산 가능한 문제를 해결할 수 있다는 것을 의미한다.첫 번째 투영기가 언제 나타났는지 아직 완전히 알 수 없다.일부는 콘라드 주저의 1941년 Z3이고, 다른 일부는 토미 프롤의 1943년 거상이라고 주장했지만, 모두가 1945년 미국인이 완성한 ENIAC이 툴링이 완성했다고 인정했다.
20세기 30년대에 도령은 정책 결정 문제를 반박하고 도령기계를 묘사하여 디지털 컴퓨터에 기반을 다졌다.1950년대 말에 이르러 그의 계산에 대한 깊은 견해는 오늘날 우리가 알고 있는 현대 디지털 컴퓨터를 탄생시켰다.불행하게도 툴링은 1954년 성적 취향으로 영국 정부의 박해를 받고 자살했다.안타깝게도 그는 현대 세계의 기적을 영원히 볼 수 없었고 창조에서 중요한 역할을 발휘했다.
유용한 리소스:

https://www.goodreads.com/book/show/5597902-complexity

https://youtu.be/t37GQgUPa6k

https://youtu.be/macM_MtS_w4uh

https://plato.stanford.edu/entries/turing-machine/