이 이야기의 영웅은 바로 앨런 튜링으로, 그는 영화 "더 게임 오브 임이테이션"에서 등장한 인물입니다.모방 게임그리고 그는 컴퓨터 과학 분야에서 두각을 나타낸 연구자를 위해 매년 수여되는 튜링상을 가지고 있습니다. 1937년에 그는 수학적으로 특정 문제가 계산될 수 없음을 증명했습니다. 그러나 이를 위해서는 "계산 가능"하다는 것을 정의해야 했고, 그 과정에서 튜링 기계를 만들었습니다. 이러한 기계는 계산의 개념을 형식화하는 추상적인 수학적 개념이며, 중요한 수학적 결과 중 하나는 특정 기계, 즉 튜링의 범용 기계가 계산 이론에서 핵심적인 역할을 한다는 것을 보여줍니다. 이 튜링의 범용 기계는 오늘날 우리가 알고 있는 컴퓨터를 구축하는 기반입니다.
튜링의 초기 논문에는 주목할 만한 내용이 몇 가지 있으며, 이는 논문의 제목에 직접적으로 나타나 있습니다 (다음은 자유 번역):계산 가능한 수와 의사 결정 문제에 대한 응용즉, 계산 가능한 수는 무엇을 의미하나요? 즉, 계산 불가능한 수가 있나요?
네, 그리고 이것을 쉽게 이해할 수 있습니다. 하지만 먼저, 계산의 초기 단계로 돌아가 보겠습니다. 왜냐하면 초기 계산은 무한 수와 밀접하게 관련되어 있기 때문입니다. 1874년, 독일 수학자 게오르크 칸트는 무한한 종류가 있다는 것을 보여주는 논문을 발표했습니다. 특히, 그는 자연수 0, 1, 2, 3...의 무한함이 실수 무한함보다 작다는 것을 보여주었습니다. 아마 당신도 간단한 그림을 통해 이미 알아젏을 것입니다. 실수 수의 무한함은 연속선(이 집합은 연속이라고 함)이며, 이 선 위에 자연수 또는 정수(이러한 다른 집합의 크기는 연속이라고 함)를 간격을 두고 삽입할 수 있습니다. 칸트는 매우 혁신적인 전략을 사용하여 연속의 요소를 한 번에 한 번, 연속의 요소와 일치시키지 않고 항상 일부 요소를 남겨두는 것이 불가능하다는 것을 보여주었습니다. 따라서 그는 연속이 연속보다 엄격하게 크다는 것을 보여주었습니다.
그래서 터링은 실수를 증명하고, 계산 불가능한 숫자가 존재한다는 것을 보여줍니다. 계산 불가능한 숫자는 항상 연속체의 요소입니다. 그의 정의에 따르면, 실수는 무한히 자릿을 인쇄하는 프로그램 또는 원래 버전인 터링 기계가 존재하면 계산 가능합니다. 그러나 각 프로그램과 각 터링 기계는 유한한 크기를 가지며 파일에 저장됩니다. 파일은 자연수이며, 매우 클 수 있습니다. 따라서 프로그램의 최대 수는 계산 가능한 무한이며, 모든 실수를 인쇄할 수 있는 충분한 프로그램이 존재할 수 없습니다. 많은 실수는 어떤 프로그램이나 터링 기계로 인쇄할 수 없으며, 이것이 계산 불가능한 실수입니다. 이제 우리는 대부분의 실수가 계산 불가능하며, 프로그램이나 터링 기계로 인쇄할 수 있는 작은 비율만이 존재한다는 것을 알고 있습니다.
여기 작은 소문이 있습니다. 터링이 1936년에 논문을 썼을 때, 터링의 지식 없이, 유명한 수학자 알론조 처치가 이미 다른 수학적 기법을 사용하여 계산 불가능한 숫자의 존재를 증명했습니다. 따라서 잡지 편집자들은 터링의 논문이 진정으로 독창적인지 의문을 제기했습니다. 논문은 테이블 위에 놓여 있었고, 누군가가 처치에게 논문을 보여달라고 요청했고, 처치는 터링의 아이디어가 매우 독창적이라고 생각하여 터링을 미국에서 박사 학위 학생으로 초대했습니다. 이러한 지연으로 인해 논문은 1937년에 처음 출판되었습니다. 터링은 1년 안에 박사 학위를 받았고, 제2차 세계 대전이 발발했을 때 영국으로 돌아왔습니다. 이것이 영화의 시작입니다.모방 게임터링이 현대 컴퓨터 과학에 대한 큰 공헌을 한 후에
숫자로 돌아가면, 사람들이 계산 불가능한 숫자가 존재한다는 것을 알게 되었을 때의 첫 번째 반응은 다음과 같습니다: "제발, 계산 불가능한 숫자의 예를 보여주세요." 그리고 저는 즐겁게 대답합니다: "보여드릴 수 없습니다. 숫자를 보여주면, 이미 계산한 것입니다. 그리고 계산 불가능한 숫자는 계산할 수 없습니다. 당연하지 않나요? 좋습니다, 당연하지 않다면, 절대 계산 불가능한 숫자를 볼 수 없다는 생각을 받아들이세요. 왜냐하면 그것이 계산 불가능하기 때문입니다."
하지만, 숫자가 계산 불가능하다면, 우리는 어떻게 그것을 정의해야 할까요? 우리는 어떤 계산도 하지 않고 간접적인 방식으로 숫자를 정의해야 합니다. 유명한 예는 "컴퓨터 프로그램이 중단될 확률"입니다. 이 표현은 숫자를 정의하는 것입니다. 이 숫자가 계산 불가능하며, 그에 대한 거의 모든 속성을 알 수 없다는 것을 증명할 수 있습니다. 이 숫자가 0.5보다 작거나 0.00000001보다 크다는 것을 알 수 없습니다. 이러한 모든 질문 또한 계산 불가능합니다.
그리고 이것은 알란 튜링의 초기 논문에 다시 우리를 데려옵니다. 그는 계산 불가능한 문제, 즉 어떤 튜링 기계도 계산할 수 없는 문제, 즉 그의 논문의 제목에 언급된 "결정 문제(순수 논리)"가 있는 문제들이 존재한다는 것을 보여주었습니다.
그리고 이것이 현대 컴퓨팅의 탄생이었으며, 컴퓨팅에는 한계가 있다는 것을 보여주었습니다. 계산 불가능한 것들이 있으며, 우리는 계산 기계로 할 수 있는 것의 한계 내에서 살아야 합니다. 튜링의 정리는 어떤 프로그래밍 언어나 컴퓨터 유형에 의존하지 않습니다. 따라서, 어떤 최첨단 인공지능이나 앞으로 100년 후에 개발될 기술이든, 계산 불가능한 문제는 여전히 계산 불가능합니다.
________________(저널 da USP에 게재된 의견)(정보 없음)본 콘텐츠의 모든 책임은 작성자에게 있으며, 이는 언론의 의견이나 상파울루 대학교의 기관적 입장을 반영하지 않습니다. 여기에서 저희의기사 작성 지침.)
