내가 가장 좋아하는 작가(데이비드 도이치,로저 펜로즈,더글러스 호프스태터)는 모두 계산 이론의 교회 튜링 논문을 탐구하며,더 중요한 것은 튜링 원리 인 가장 강력한 해석을 탐구합니다. 이 게시물에서 나는 먼저 평신도의 용어로 교회 튜링 논문을 설명 할 것이다.
컴퓨터과학 학위를 공부하던 시절,전산이론 수업에서 튜링 머신과 교회 튜링 논문을 공부했다. 그때 나는 그것이 큰 시간 낭비라고 생각했다. 나는 단지 컴퓨터를 프로그래밍하고 싶었고이 오랫동안 죽은 튜링 사람(이 교회 사람)이나 그의 어리석은 이론 기계에 대해 덜 신경 쓸 수 없었습니다.
이제 나는 교회-튜링 논문의 철학적 파급 효과를 이해 했으므로,나는 수업 시간에 관심을 가졌 으면 좋겠다! 왜냐하면 교회-튜링 논문은 사실이라면 심오한 철학적 파급 효과를 가지고 있으며 현실의 깊고 특별한 본질에 대해서도 말해 줄 수 있기 때문입니다.
유한 오토마타
계산 이론에 대한 모든 텍스트와 클래스는”유한 오토마타”라고 불리는 것으로 시작됩니다.”그들 뒤에 기본 아이디어는 꽤 쉽습니다. 당신은 단지 선택을하고 상태 사이를 이동할 수있는 간단한’기계’를 상상합니다. 동전 운영한 십자형 회전식 문의”논리”를 대표하는 아주 간단한 것의 보기는 여기 있다.
일반 영어로,이것은 당신이 잠겨있는 십자형 회전식 문을 통해 밀어하려고하면 먼저 동전에 넣어하지 않은 경우,당신은 할 수 없다고 말한다. 당신이 동전에 넣어 가지고 있지만 아직 통해 밀어하지 않은 경우,추가 동전은 잠금 해제 상태로 둡니다. 당신이 동전에 넣어 한 경우,당신은 통해 밀어 수 있습니다. 그런 다음 다음 사람을 위해 다시 잠급니다.
아마도 설명보다 다이어그램에서 이해하는 것이 더 쉬울 것입니다.
유한 오토마타는 이보다 훨씬 더 복잡한 논리를 수행 할 수 있습니다. 그러나 이것은 당신에게 유한 오토마타가 어떻게 작동하는지에 대한 기본적인 느낌을 줄 것입니다.
한 가지 주목해야 할 것은 유한 오토 마톤은,위와 같은,그것은 단지 종이에 거품과 라인의 무리로 존재하기 때문에 순수 이론이다. 그것은 이 결정을 내리는 십자형 회전식 문 안쪽에 약간 작은”유한 자동 기계 기계”가 있는 처럼 이지 않습니다. 아니면 내가 대신 십자형 회전식 문 자체가 유한 자동 기계라고 말해야한다.
우리가 정말로 원한다면,우리는 아마도 유한 한 오토 마톤이 될 실제 생활에서 기계를 만들 수 있습니다.실생활에 있는 진짜 기계로 그것을 건설하고 십자형 회전식 문으로 그 후에 설치하기에서 누군가를 멈추는 아무것도 없습니다. 그것은 단지 그것을 할 수있는 가장 저렴한 방법이 아닙니다.
따라서 유한 오토 마톤의 그림으로 만드는 모든’프로그램’은 실제로 작동하는 실제”계산”으로 바뀔 수 있습니다. 실제로 존재할 수있는 계산 기계(유한 오토 마톤과 같은)와 단지 가설적이고 물리 법칙을 위반하는 기계 간의 차이의 중요성은 한 순간에 중요합니다.
더 강력한 기계
전산 이론의 클래스가 진행됨에 따라,학생들은 유한 오토마타보다 더 강력한 점점 더 복잡한’기계’에 도입된다. 오른쪽 그림에서 볼 수 있듯이,다음으로 가장 강력한 것은 푸시다운 오토마타입니다. “메모리”의 일종 추가와 함께. 여기서 중요한 점은 결정론적인 유한 오토마톤에 쓸 수 없는 특정 유형의 프로그램이 있다는 점이다. 따라서”연산 능력”의 관점에서 연산 능력과 연산 능력 사이에는 관계가 있다.”즉,디파에 작성된 모든 프로그램이 또한 디파에 기록 될 수 있다는 것을 증명할 수 있지만 그 반대는 사실이 아닙니다.
그냥”메모리 기능”을 사용하지 마십시오.
하지만 그 반대는 어떻습니까? 특정 유형의”프로그램”을 사용하여 번역하는 것이 불가능하다는 것을 증명할 수 있습니까? 즉,푸시 다운 오토마타가 유한 오토마타에 매핑 될 수 없다는 증거가 있습니까? 또는 우리는 단지 유한 오토마타가 푸시 다운 오토마타보다 덜 강력하다고 가정하고 있습니까? 이 응용 프로그램은 당신에게 아름다운 욕실 꾸미기의 갤러리를 보여줍니다. 그것은 적어도 가능성이 아닌가?
밝혀진 바와 같이,특정 유형의 프로그램을 실행할 수 있다는 것을 증명할 수 있다. 당신이 그것을 할 방법은 당신이 계산을 찾을 것입니다(즉, 프로그램)은 디파가 계산할 수 없다는 것을 증명할 수 있고 그 다음에 디파가 그것을 계산할 수 있다는 것을 입증 할 수 있습니다.
컴퓨터의 연산 능력
이 사실은—더 강력한 논리 기계가 있다는 것—그 자체로 흥미 롭습니다.
그러나 그것은 철학적 질문으로 이어집니다:”가장 강력한 컴퓨팅 기계 같은 것이 있습니까?”
그러한”가장 강력한 기계”가 있다면,제안 된 특정 기계가”가장 강력한 기계”라는 것을 어떻게 알 수 있습니까?”아니면 다른 유형의 컴퓨터 만 사용할 수 있으며 작업에 적합한 컴퓨터를 선택해야합니까?
튜링 기계
그래서 어떤 기계가
역사가 그러하듯이,거의 동시에 두 가지 매우 다른 유형의”기계”가 제안되었는데,이 두 가지 유형 모두 극지방보다 훨씬 강력했다.
하나는 앨런 튜링의 튜링 기계였습니다. 다른 하나는 기계를 개발하는 것과 같은 목적을 이룬 알론조 교회가 개발한 영리한 표기법만큼 기계가 아니었습니다. 이 두 가지”기계”중 튜링 기계는 개념적으로 가르치기가 더 쉽기 때문에 일반적으로 계산 이론 과정에서 가르치는 기계입니다.
튜링 기계는 읽기/쓰기 헤드와 읽거나 쓸 수있는(가상의)종이 테이프가있는 재미있는 작은 이론적 기계입니다. 튜링 머신이 읽는 것을 기반으로 튜링 머신은 읽기/쓰기 헤드를 앞으로 또는 뒤로 이동하거나 테이프의 새 위치에서 읽거나 테이프의 새 위치를 쓰는 것으로 구성된 일종의 작업을 수행하는 작업 상태로 만듭니다. 튜링 기계는 다음과 같습니다:
튜링 기계 및 현대 컴퓨터
관심의 한 가지 튜링 기계는,표면 외관에도 불구하고,실제로 현대 컴퓨터와 매우 유사하다는 것이다. 현대 컴퓨터에서 중앙 처리 장치(중앙 처리 장치)는 튜링 기계의 읽기/쓰기 헤드와 동일합니다. 메모리 칩(램 또는 롬)은 터닝 머신이 읽거나 쓸 수있는 긴 종이 테이프의 셀과 매우 유사합니다. 그래서 현대 컴퓨터는 튜링 기계와 거의 동등한 것 같습니다.
현대 컴퓨터는 튜링 기계에 비해 한 가지 장점이 있습니다. 현대 컴퓨터는 튜링 기계처럼 순차적으로”메모리”의 한 셀에서 이동할 필요가 없습니다.
튜링 기계가 한 번에 하나의 셀만 움직일 수 있다는 사실은 상당한 제한처럼 보입니다. 우리는 일부 기계가 다른 기계보다 논리적으로’더 강력한’방법을 보았습니다. 그래서 아마도 튜링 기계보다 더 강력한 기계가 튜링 기계가 할 수없는 작업을 수행 할 수 있습니까? 그리고 어쩌면 현대 컴퓨터—순차적으로 셀에서 셀로 이동해야하는 것보다 메모리 주위를 뛰어 다니는 능력으로 인해—튜링 기계가 할 수없는 일부 프로그램을 실행할 수 있습니까?
사실 현대 컴퓨터는 실제로 튜링 기계보다 표현력이 떨어진다. 그러나 일반적으로 이것은 인간이 일반적으로 무한히 긴 결과를 제공하는 무한히 긴 계산에 관심이있는 것은 아니기 때문에 어떤 유형의 계산을 수행 할 수 있는지에 거의 차이가 없습니다. 그래서 저는 현대 컴퓨터와 튜링 기계가”대략”동등하다고 말합니다. 사실,임의적이지만 유한 한 크기의 메모리를 가정하는 한,실행할 수있는 프로그램 유형의 측면에서 정확히 동일합니다.
교회 튜링 논문:튜링 기계=최대 논리적 힘
그러나 가난한 알론조 교회는 어떻습니까? 튜링 기계가 가르치기 쉽기 때문에 그의 불쌍한”기계”는 잊어 버렸습니다. 그의 기계는 튜링 기계가 할 수없는 계산/프로그램을 표현할 수 있습니까?
앨런 튜링과 알론조 교회가 완전히 다른 두 가지 유형의 이론적 계산 기계를 만들었고 그들이 수행 할 수있는 계산 유형의 측면에서 정확히 동일한 일이 일어난다면 별의 우연이 아니겠습니까?
앨런 튜링이 튜링 기계를 위해 작성된 모든 프로그램이 교회 기계를 위해 작성 될 수 있다는 증거와 교회 기계를 위해 작성된 모든 프로그램이 튜링 기계를 위해 작성 될 수 있다는 증거를 만들 수 있었을 때 모든 사람들의 놀라움을 상상해보십시오.
실제로,이론적인 계산 기계의 다수 제시한 유형이 있습니다. 예를 들어,이론가들은 튜링 기계가 여러 개의 테이프를 읽고 쓸 수 있도록 허용하려고했습니다. 그들은 심지어 튜링 기계에 2 차원’시트’를 읽고 쓸 수 있도록 시도했습니다. 이론가들은 튜링 기계(및 교회 기계)에 대한 모든 종류의 개선을 시도했습니다.
그리고 지금까지 그것들이 단순한 튜링 기계와 동등하다는 것을 그들 하나 하나에 대한 증거를 생성하는 것이 가능했다.
그것은 야생 우연의 일치처럼 보이지 않습니까? 그리고 어떤 유형의 계산을 수행 할 수 있는지에 대한 상단이 제한되지 않는 한 그것은 야생 우연의 일치가 될 것입니다.
이러한 상한이있는 경우,그것은 전혀 우연이 없을 것 튜링 기계와 교회 기계 및 다른 모든 계산 기계는 모두 단지 같은 계산 능력을 가지고 일어날 제안,사실 때문에 그들은 모두 동등한 이유는 우리가 계산 능력의 상한에 도달했기 때문이다.
그러나 우리는 튜링 기계가 할 수없는 계산을 수행 할 수있는 능력을 가진 계산 기계가 없다는 것을 증명할 수 있습니까?
정확히 어떻게 그런 증거를 만들 수 있을까요? 사실 우리는 튜링 기계보다 더 강력한 것은 없다는 것을 증명할 수 없습니다. 그래서,누가 알 겠어,아마있다.
그러나 사실은 우리가 그러한 기계를 발견(또는 발명)할 수 없다는 것입니다.
따라서 튜링 기계의 힘을 향상시킬 수있는 방법을 찾기 위해 상당한 노력을 기울이고 실패한 후에 마침내 교회 튜링 논문은 그것이 사실이라고 입증되지 않았음에도 불구하고 받아 들여졌습니다. 교회 튜링 논문은 본질적으로 다음과 같이 말합니다:
평범한 오래된 튜링 기계가 할 수없는 논리 프로그램을 수행 할 수있는 계산 기계의 어떤 종류를 마련 할 수 없습니다.
또는 다른 말로:
튜링 기계와 그 등가물은 가능한 가장 강력한 유형의 계산 기계이며 우리가 아직 모르는 강력한 기계는 없습니다.
이 논문에 대한 수년간의 연구 끝에,이 논문은 여전히 기본적으로 보유하고있다. 우리는 이론적 양자 컴퓨터의 도입과 함께 논문에 다소 수정 된 것을 나중에 볼 수 있습니다. 그러나 기본적으로 논문은 오늘날에도 여전히 사실입니다. 논리적 표현력과 관련하여 튜링 기계를 능가 할 수있는 방법을 생각해 낸 사람은 아무도 없습니다. 튜링 기계는 여전히 일등 챔피언입니다.
이제 당신은 교회 튜링 논문을 이해합니다. 그러나,교회 튜링 논문은 정말 튜링 원칙에 매우 동일하지 않습니다. 그래서 미래의 포스트에서 나는 그 차이가 무엇인지,그리고 그것이 철학적 파급 효과가 무엇인지 개발할 것입니다.
노트
튜링 원리. 그래서(적어도 현재의 형태로)그것을 믿지 않는 로저 펜로즈에 의해 명명. 그것은 데이비드 도이치에 의해 튜링-도이치 원칙으로 개발되었으며,그는 적어도 그의 형태로 그것을 믿는다.)(자세한 내용은 위키 백과의 문서를 참조하십시오)