위키원
"튜링불완전"의 두 판 사이의 차이
(→영향과 전망) |
|||
| 1번째 줄: | 1번째 줄: | ||
'''튜링불완전'''(Turing Incomplete)은 수리논리학에서 페아노 공리계를 포함하는 모든 무모순적 공리계는 참인 일부 명제를 증명할 수 없으며, 특히 스스로의 [[무모순성]]을 증명할 수 없다는 정리다. | '''튜링불완전'''(Turing Incomplete)은 수리논리학에서 페아노 공리계를 포함하는 모든 무모순적 공리계는 참인 일부 명제를 증명할 수 없으며, 특히 스스로의 [[무모순성]]을 증명할 수 없다는 정리다. | ||
==역사와 배경== | ==역사와 배경== | ||
| + | ===[[쿠르트 괴델]]=== | ||
| + | *20세기의 첫 30년 동안에 사람들은 대부분의 고전수학의 [[무모순성]]이 [[자연수]]의 산술에서의 대응되는 결과에 의존함을 알게 되었다. | ||
*수학이 직관과 상식을 벗어나 형식화, 추상화되면서, 체계의 근거로 사용되는 공준의 집합체가 내적으로 모순되지 않고, 따라서 "공준에서 서로 모순되는 정리가 추론되는 경우는 없는가"라는 무모순성의 문제가 제기되었는데 형식적인 수학에서는 '진리'와 '증명가능성'의 개념이 구별되어 쓰인다. 즉, 한 공리 체계에서 연역적으로 어떤 정리를 도출할 수 있으면 그 정리는 증명가능한 것인데, 그 체계 내에서 거짓임을 증명할 수 없는 어떤 진술이 항상 참임을 증명할 수 있다는 보장은 하지 않는다. | *수학이 직관과 상식을 벗어나 형식화, 추상화되면서, 체계의 근거로 사용되는 공준의 집합체가 내적으로 모순되지 않고, 따라서 "공준에서 서로 모순되는 정리가 추론되는 경우는 없는가"라는 무모순성의 문제가 제기되었는데 형식적인 수학에서는 '진리'와 '증명가능성'의 개념이 구별되어 쓰인다. 즉, 한 공리 체계에서 연역적으로 어떤 정리를 도출할 수 있으면 그 정리는 증명가능한 것인데, 그 체계 내에서 거짓임을 증명할 수 없는 어떤 진술이 항상 참임을 증명할 수 있다는 보장은 하지 않는다. | ||
| + | *1929년,알파벳의 글자들과, 그것들의 결합인 단어와 문장들을, 수치부호(numerical code)로써 표현하는 법을 창안해 냈다. | ||
*1931년, [[괴델]]은 20대의 나이에 학계를 깜짝 놀라게 한 세기적 결과인 불완전성 정리를 발표,‘진리임에도 증명될 수 없는 수학적 [[명제]]가 존재한다’는 것이다.그의 정리는 제일, 제이 불완전성 정리들로 나눠진다. 제일 [[불완전성 정리]]는 대략적으로 서술하면, 수학에서는 증명도 부정도 되지 않는 명제가 반드시 존재한다는 것이다.그는 [[칸토어]]의 연속체의 가설이 수학에서 ‘부정되지 않는 명제’임을 증명하는데 성공한다. 그 후 1960년대에 와 비로소 코헨(Paul J. Cohen)이란 젊은 수학자에 의해 연속체 가설이 ‘증명도 되지 않는 명제’임이 밝혀짐으로 연속체 가설 문제의 종지부가 찍힌다.제이 불완전성 정리는 더욱 놀랍다. 수학을 전개하는 근본 공리를 선정해 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실 자체는 (그 체계의 논리전개로는) 증명을 할 수 없다는 것이다. 괴델의 정리는 힐베르트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여겼던 믿음이 옳지 않다는 것이다. 이는 인간 인식을 형식화 또는 기계화하는 것에 근본적인 한계가 있음을 매우 분명하게 보여준 하나의 세기적 사건이었다.제일, 제이 정리를 한마디로 요약하면, ‘진리이나 증명되지 않는 수학적 명제가 존재한다’이다. 제이 정리의 경우, 방금 살핀 것과 같이, ‘수학에 모순이 없다’는 명제 자체는[[진리]]여야 함에도, 증명될 수 없다는 것이다. 제일 정리의 경우도, 수학에서 증명도 반증도 되지 않는 명제는, 플라톤적 관점에서 그 자신 또는 자신의 부정명제 둘 중 하나는 참일 수밖에 없으나, 어느 것도 증명되지 않는다.괴델은 참인 수학적 명제들의 범위가, 인간이 궁극적으로 증명의 방법을 통해 참으로 확인해 인식할 수 있는 명제들의 범위를 넘어선 것을 보인 것이다. 이를 위해 우선 `인간이 참으로 인식 또는 증명할 수 있는 명제'들의 범위를 규정하기 위해 `계산 가능하다'는 개념을 최초로 제안하게 된다.후에 [[앨런 튜링]]과 후대 학자들에 의해 정의가 확장 보강되고, 튜링은 그렇다면 기계적 [[프로그램]]으로 `계산 가능하다는 개념'을 실행하는 장치를 만들 수 있지 않을까 생각했고, 실제 컴퓨터를 설계하기에 이른 것이다. <ref>〈[https://terms.naver.com/entry.nhn?docId=3570783&cid=58944&categoryId=58970 괴델의 불완전성 정리]〉, 《네이버 지식백과》</ref> | *1931년, [[괴델]]은 20대의 나이에 학계를 깜짝 놀라게 한 세기적 결과인 불완전성 정리를 발표,‘진리임에도 증명될 수 없는 수학적 [[명제]]가 존재한다’는 것이다.그의 정리는 제일, 제이 불완전성 정리들로 나눠진다. 제일 [[불완전성 정리]]는 대략적으로 서술하면, 수학에서는 증명도 부정도 되지 않는 명제가 반드시 존재한다는 것이다.그는 [[칸토어]]의 연속체의 가설이 수학에서 ‘부정되지 않는 명제’임을 증명하는데 성공한다. 그 후 1960년대에 와 비로소 코헨(Paul J. Cohen)이란 젊은 수학자에 의해 연속체 가설이 ‘증명도 되지 않는 명제’임이 밝혀짐으로 연속체 가설 문제의 종지부가 찍힌다.제이 불완전성 정리는 더욱 놀랍다. 수학을 전개하는 근본 공리를 선정해 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실 자체는 (그 체계의 논리전개로는) 증명을 할 수 없다는 것이다. 괴델의 정리는 힐베르트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여겼던 믿음이 옳지 않다는 것이다. 이는 인간 인식을 형식화 또는 기계화하는 것에 근본적인 한계가 있음을 매우 분명하게 보여준 하나의 세기적 사건이었다.제일, 제이 정리를 한마디로 요약하면, ‘진리이나 증명되지 않는 수학적 명제가 존재한다’이다. 제이 정리의 경우, 방금 살핀 것과 같이, ‘수학에 모순이 없다’는 명제 자체는[[진리]]여야 함에도, 증명될 수 없다는 것이다. 제일 정리의 경우도, 수학에서 증명도 반증도 되지 않는 명제는, 플라톤적 관점에서 그 자신 또는 자신의 부정명제 둘 중 하나는 참일 수밖에 없으나, 어느 것도 증명되지 않는다.괴델은 참인 수학적 명제들의 범위가, 인간이 궁극적으로 증명의 방법을 통해 참으로 확인해 인식할 수 있는 명제들의 범위를 넘어선 것을 보인 것이다. 이를 위해 우선 `인간이 참으로 인식 또는 증명할 수 있는 명제'들의 범위를 규정하기 위해 `계산 가능하다'는 개념을 최초로 제안하게 된다.후에 [[앨런 튜링]]과 후대 학자들에 의해 정의가 확장 보강되고, 튜링은 그렇다면 기계적 [[프로그램]]으로 `계산 가능하다는 개념'을 실행하는 장치를 만들 수 있지 않을까 생각했고, 실제 컴퓨터를 설계하기에 이른 것이다. <ref>〈[https://terms.naver.com/entry.nhn?docId=3570783&cid=58944&categoryId=58970 괴델의 불완전성 정리]〉, 《네이버 지식백과》</ref> | ||
2019년 8월 1일 (목) 13:07 판
튜링불완전(Turing Incomplete)은 수리논리학에서 페아노 공리계를 포함하는 모든 무모순적 공리계는 참인 일부 명제를 증명할 수 없으며, 특히 스스로의 무모순성을 증명할 수 없다는 정리다.
역사와 배경
쿠르트 괴델
- 20세기의 첫 30년 동안에 사람들은 대부분의 고전수학의 무모순성이 자연수의 산술에서의 대응되는 결과에 의존함을 알게 되었다.
- 수학이 직관과 상식을 벗어나 형식화, 추상화되면서, 체계의 근거로 사용되는 공준의 집합체가 내적으로 모순되지 않고, 따라서 "공준에서 서로 모순되는 정리가 추론되는 경우는 없는가"라는 무모순성의 문제가 제기되었는데 형식적인 수학에서는 '진리'와 '증명가능성'의 개념이 구별되어 쓰인다. 즉, 한 공리 체계에서 연역적으로 어떤 정리를 도출할 수 있으면 그 정리는 증명가능한 것인데, 그 체계 내에서 거짓임을 증명할 수 없는 어떤 진술이 항상 참임을 증명할 수 있다는 보장은 하지 않는다.
- 1929년,알파벳의 글자들과, 그것들의 결합인 단어와 문장들을, 수치부호(numerical code)로써 표현하는 법을 창안해 냈다.
- 1931년, 괴델은 20대의 나이에 학계를 깜짝 놀라게 한 세기적 결과인 불완전성 정리를 발표,‘진리임에도 증명될 수 없는 수학적 명제가 존재한다’는 것이다.그의 정리는 제일, 제이 불완전성 정리들로 나눠진다. 제일 불완전성 정리는 대략적으로 서술하면, 수학에서는 증명도 부정도 되지 않는 명제가 반드시 존재한다는 것이다.그는 칸토어의 연속체의 가설이 수학에서 ‘부정되지 않는 명제’임을 증명하는데 성공한다. 그 후 1960년대에 와 비로소 코헨(Paul J. Cohen)이란 젊은 수학자에 의해 연속체 가설이 ‘증명도 되지 않는 명제’임이 밝혀짐으로 연속체 가설 문제의 종지부가 찍힌다.제이 불완전성 정리는 더욱 놀랍다. 수학을 전개하는 근본 공리를 선정해 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실 자체는 (그 체계의 논리전개로는) 증명을 할 수 없다는 것이다. 괴델의 정리는 힐베르트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여겼던 믿음이 옳지 않다는 것이다. 이는 인간 인식을 형식화 또는 기계화하는 것에 근본적인 한계가 있음을 매우 분명하게 보여준 하나의 세기적 사건이었다.제일, 제이 정리를 한마디로 요약하면, ‘진리이나 증명되지 않는 수학적 명제가 존재한다’이다. 제이 정리의 경우, 방금 살핀 것과 같이, ‘수학에 모순이 없다’는 명제 자체는진리여야 함에도, 증명될 수 없다는 것이다. 제일 정리의 경우도, 수학에서 증명도 반증도 되지 않는 명제는, 플라톤적 관점에서 그 자신 또는 자신의 부정명제 둘 중 하나는 참일 수밖에 없으나, 어느 것도 증명되지 않는다.괴델은 참인 수학적 명제들의 범위가, 인간이 궁극적으로 증명의 방법을 통해 참으로 확인해 인식할 수 있는 명제들의 범위를 넘어선 것을 보인 것이다. 이를 위해 우선 `인간이 참으로 인식 또는 증명할 수 있는 명제'들의 범위를 규정하기 위해 `계산 가능하다'는 개념을 최초로 제안하게 된다.후에 앨런 튜링과 후대 학자들에 의해 정의가 확장 보강되고, 튜링은 그렇다면 기계적 프로그램으로 `계산 가능하다는 개념'을 실행하는 장치를 만들 수 있지 않을까 생각했고, 실제 컴퓨터를 설계하기에 이른 것이다. [1]
개요
비트코인의 스크립트 언어는 비교적으로 단순해서 비트코인이 화폐로서의 역할만 수행하괴델의 정리는 힐베르트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여겼던 믿음이 옳지 않다는 것이다. 이는 인간 인식을 형식화 또는 기계화하는 것에 근본적인 한계가 있음을 매우 분명하게 보여준 하나의 세기적 사건이었다. [네이버 지식백과] 괴델의 불완전성 정리 - 참이지만 증명할 수 없는 수학적 명제가 있다? (수학산책, 과학창의재단, 김병한)게끔 한다. 예를 들어, 현재 다양한 언어가 전 세계적으로 사용되고 있지만 비트코인의 스크립트 언어는 원시시대의 인류가 처음 등장했을 때 사용했던 매우 단순하고 표현방법이 많지 않은 언어라고 비유를 들 수 있다.[2] 이를 비트코인의 튜링불완전성이라고 한다.
물론 비트코인 스크립트 언어로도 할 수 있는 작업이 많지만, 모든 경우의 프로그래밍을 다 지원하지는 못한다.[3] 특히 while 이나 for과 같이 순환(loop) 명령 카테고리가 빠져있다. 이는 비트코인의 결함이기도 하지만 의도된 것인데, 비트코인은 무한 반복 공격을 방지하기 위해 순환 명령어를 없앴다. 이론적으로 튜링불완전성은 스크립트 프로그래머가 극복할 수 있는 장애물이기는 하다.[4] 어떤 순환 명령이든 단순히 하위 코드를 여러 차례 if 구문과 함께 반복하여 구현하는 것이 가능하기 때문이다.[5] 하지만 이는 매우 공간 비효율적인 프로그램이 된다. 예를 들어 타원곡선 서명 알고리즘을 실행하기 위해서 코드 안에 있는 곱셈을 모두 개별적으로 256번 반복하는 과정이 필요하기 때문이다.[6]
비트코인이 튜링불완전한 스크립트를 사용하는 반면에 이더리움은 튜링완전한 언어인 솔리디티(Solidity)와 서펀트(Serpent)를 사용한다. 이는 복잡한 다중계약인 스마트 계약을 가능하게 하며 분산 어플리케이션을 구현한다. 튜링불완전성을 갖는 프로그램도 튜링 완전성을 갖는 프로그램과 동일한 계약을 생성할 수는 있지만, 만약 튜링완전성이 없을 경우 다루기가 매우 어려우며, 이러한 한계로 인해 계약의 활용도가 매우 제한적일 수밖에 없다.[7]
- 이더리움의 스마트 계약 플랫폼
- 이더리움(Ethereum)은 비트코인 스크립트 시스템의 튜링 불완전성이라는 한계를 극복하고자 나온 스마트 컨트랙트 플랫폼(smart contract platform)이다. 비탈릭 부테린(Vitalik Buterin)이 창시한 이더리움 블록체인의 경우, 블록에 데이터뿐만 아니라 비트코인 스크립트 시스템의 한계인 조건문(if), 반복구문(loop) 등의 실행 코드를 포함시켜 로직의 실행을 자동화할 수 있다. 스마트 컨트랙트를 구현하기 위한 컨트랙트 코드(contract code)는 이더리움 가상머신(EVM; Ethereum Virtual Machine)이라는 독립된 실행 환경에서 실행된다. 여기에 스마트 컨트랙트를 실행할 때마다 수수료인 가스(gas)를 발생시키고 네트워크상에 수수료의 한계를 설정하여 무한루프를 막았다. 무한히 반복되는 조건을 만들어 스마트 컨트랙트를 실행시키면 중간에 수수료 한계점에 도달하게 되는데, 이때 중단된다.
- 이더리움에서 스마트 컨트랙트는 솔리디티(Solidity) 언어로 프로그래밍된다. 솔리디티 언어로 프로그래밍된 스마트 컨트랙트는 컴파일러(solc)에 의해 바이트코드(bytecode)로 컴파일되고, 컴파일된 바이트코드는 블록에 포함되어, 이더리움 가상머신(EVM)에 의해 실행된다. 이더리움 가상머신(EVM)은 이더리움 스마트 컨트랙트의 바이트코드를 실행하는 32 바이트 스택 기반의 실행환경이다. 이더리움이 제공하려는 것은 튜링 완전(turing-complete) 프로그래밍 언어가 심어진 블록체인이다. 이 프로그래밍 언어는 코딩된 규칙에 따라 '어떤 상태'를 '다른 상태'로 변환시키는 기능(arbitrary state transition functions)이 포함된 계약을 사용자들이 직접 작성할 수 있게 함으로써, 인간이 상상할 수 있는 모든 종류의 계약을 스마트 컨트랙트로 만들 수 있다. 이를 통해 모든 계약이 자동으로 실행할 수 있고, 이를 위한 다양한 분산형 애플리케이션인 디앱(DApp)도 만들 수 있다.[8] 누구든지 솔리디티 언어를 사용해 스마트 컨트랙트와 디앱을 작성하고 소유권에 대한 임의의 규칙, 트랜잭션 형식(transaction format), 상태변환함수(state transition function) 등을 생성할 수 있다.
이더리움에 대해 자세히 보기
영향과 전망
- 불완전성 정리로 힐베르트의 원래 의도 했던 계획이 무산됐다고 해서 그의 형식주의가 사라진 것은 아니다. 그가 처음 제시했던 수학의 형식적 재구성에 관한 철학과 관점은 계속 유효하고 올바른 방향이라 여겨졌고, 현대수학은 그의 형식주의의 발전에 바탕을 두고 있다. 즉, 인간의 근본적 인식의 한계로 인해 힐베르트가 원하던 것을 100% 얻을 순 없다 하더라도, 그의 주장은 기본적으로 옳았다는 것이다. 따라서 불완전성 정리는 칸토어 이후 제기돼 왔던 수학 기초론의 기본 논의를 무너뜨린 것이 아니라, 오히려 문제의 본질을 드러내고 한계 속에서도 계속 작업을 해야 함을 알려 준 것이다. 따라서 이후, 대부분의 수학자들이 수학기초론의 근본적 인식에 동의하게 되는 계기를 마련해, 출렁이던 초기 수리논리학 역사가 안정되고 급속한 후속 진보를 이루는 토대가 된 것이다.뿐만 아니라 괴델의 불완전성 정리는 분석철학, 인식론에 영향을 미치고 있으며, 언어학, 현대의 인지과학에 까지 파급력을 끼치고 있다. 논리학 내에서는 정리의 확장이, 양상논리라는 형태로 발전해 오늘에 이른다. 정리의 증명에 사용된 코딩이론, 계산가능성론 등은 후대 튜링, 폰 노이만(von Neumann) 등에 의해 발전돼, 세계 최초의 현대적 컴퓨터 설계를 위한 이론 배경이 된다.
2006년에는 괴델의 탄생 백주년을 맞아 오스트리아 비엔나 대학에서 기념학술대회가 개최됐다. 여러 분야의 학자들이 참가했으며 괴델의 우주론, 이론 컴퓨터 학에 미친 괴델의 공헌에 대한 발표가 있었다. 괴델의 업적이 신학, 철학 등의 인문학과 인지과학에 미친 영향은 매우 컸다.. 그의 주 연구 분야였던 집합론, 수리논리학에서 현대에도 계속되는 영향과 결과들의 발전에 대한 발표가 뒤를 이었다. 그와 그의 업적에 대한 향연은 끝난 것이 아니라 세월이 흐를수록 더욱 커져가고 있다.
각주
- ↑ 〈괴델의 불완전성 정리〉, 《네이버 지식백과》
- ↑ easyblockchain, 〈쉽게 설명하는 블록체인 : 이더리움이란?〉, 《뱅크샐러드》, 2018-05-19
- ↑ yahweh87, 〈# 35 – 이더리움 백서(4편)〉, 《스팀잇》
- ↑ 람보짱, 〈이더리움 한글 백서〉, 《네이버 블로그》, 2018-01-14
- ↑ 야옹메롱, 〈(이더리움) White Paper 백서 풀이 및 해석〉, 《네이버 블로그》, 2018-10-12
- ↑ Vitalik Buterin, 〈차세데 스마트 컨트랙트와 탈중앙화된 어플리케이션 플랫폼(A Next-Generation Smart Contract and Decentralized Application Platform〉, 《이더리움 코리아》
- ↑ 어미새, 〈이더리움 백서(11편)〉, 《네이버 블로그》, 2018-04-20
- ↑ Vitalik Buterin, "A Next-Generation Smart Contract and Decentralized Application Platform", 2013.
참고자료
- Vitalik Buterin, 〈차세데 스마트 컨트랙트와 탈중앙화된 어플리케이션 플랫폼(A Next-Generation Smart Contract and Decentralized Application Platform〉, 《이더리움 코리아》
- 〈괴델의 불완전성 정리〉, 《네이버 지식백과》
같이 보기
