[이더리움과 월드 컴퓨터] 1-2. 튜링 완전과 튜링 불완전

이전글

[이더리움과 월드 컴퓨터] 1-1. 블록체인: 단일 장부와 단일 메모리

 

튜링 완전과 튜링 불완전

 

 이번 글에서는 이전 글에서 소개했던 범용 블록체인이 가진 문제점에 대해 살펴보겠습니다.

 

I. 튜링 머신

 범용 블록체인이 가진 문제점을 이해하기 위해서는 튜링 완전과 튜링 불완전의 의미를 이해해야 합니다. 그리고 이를 이해하기 위해서는 튜링 머신이 무엇인지에 대해 먼저 알아야 합니다.

 

 튜링 머신은 앨런 튜링이 1936년 발표한 논문에서 등장한 가상의 기계입니다. 당시 앨런 튜링은 모든 수학적 문제를 해결할 수 있는 기계(알고리즘)가 존재하는지에 관한 문제의 새로운 방식의 증명을 제시하고자 했습니다. 해당 문제를 조금 더 자세히 설명해 보면 다음과 같습니다.

 

 예를 들어 어떤 수학 공식에 다른 공식들을 무작위로 대입하여 정리하는 특정한 방식이 존재한다고 가정해 보겠습니다. 이 과정 속에서 뉴턴의 만유인력 공식이나 아직 밝혀지지 않았던 공식들이 유도될지도 모릅니다. 즉, 지금까지 풀렸거나 풀리지 못했던 여러 수학 문제들이 풀릴지 모릅니다. 만약 이 과정을 특정한 알고리즘을 가진 기계장치가 해낼 수 있다면, 지금까지 난제로 밝혀진 모든 문제를 자동으로 해결할 수 있을지 모릅니다.

 

 앨런 튜링은 해당 문제를 증명하기 위해 실제로 모든 수학적 연산을 수행할 수 있는 보편적인 연산 기계를 제시하고, 이 기계가 모든 수학적 문제를 해결할 수 있는지에 대해 증명했습니다. 그 결과 이전 증명처럼 모든 수학적 문제를 해결할 수 있는 기계는 존재할 수 없다는 결론을 내리게 되었습니다.

 

 앨런 튜링이 튜링 머신의 개념을 처음 제시한 이후, 모든 종류의 튜링 머신을 흉내 낼 수 있는 보편 만능 기계라는 개념이 등장합니다. 이것이 바로 우리가 오늘날 컴퓨터라고 부르는 기계입니다.

 

II. 튜링 완전

 만약 보편 만능 기계가 수행할 수 있는 모든 기능을 수행할 수 있다면, 이를 튜링 완전하다고 합니다. 또한 프로그래밍 언어 중 이러한 기능을 모두 수행할 수 있도록 설계되었다면, 해당 언어를 튜링 완전한 언어라고 부릅니다.

 

 이러한 튜링 완전함에는 큰 약점이 있습니다. 이 약점을 이해하기 위해서는 1936년 앨런 튜링의 논문을 들여다봐야 합니다. 해당 논문에서 앨런 튜링은 튜링 머신이 모든 수학적 문제를 해결할 수 없다는 것을 증명하기 위해 모든 수학적 문제를 해결할 수 있다는 명제에 반례를 들었습니다. 그리고 이 반례가 그 유명한 튜링 정지 문제입니다.

 

 튜링 정지 문제는 다음과 같습니다. 예를 들어 어떤 튜링 머신 H가 다른 튜링 머신이 연산을 수행하는 과정에서 무한 루프가 발생하는지를 판별할 수 있다고 가정해 보겠습니다. 만약 다른 튜링 머신이 어떠한 연산을 수행하였을 때 무한 루프가 발생한다면 튜링 머신 H는 참을, 그 외에는 거짓을 반환할 것입니다.

 

 

 여기에 새로운 튜링 머신 N이 있다고 가정해 보겠습니다. 튜링 머신 N은 튜링 머신 H의 결과를 반대로 수행하는 기계입니다. 예를 들어 튜링 머신 H가 다른 튜링 머신이 동작하는 과정에서 무한 루프가 발생하지 않을 것이라고 판별한다면, 튜링 머신 N은 이 결과를 받아서 반대로 무한 루프가 발생하도록 출력합니다. 만약 H가 무한 루프가 발생할 것이라고 판단한다면, N은 결과를 받아 무한 루프가 발생하지 않도록 정지할 것입니다.

 

 

 이러한 두 기계를 하나로 묶어 HN이라는 튜링 머신이 존재한다고 가정해 보겠습니다. HN은 다른 튜링 머신이 무한 루프에 빠질 것이라고 판단한다면 멈추며, 다른 튜링 머신이 무한 루프에 빠지지 않을 것이라고 판단한다면 무한 루프에 빠질 것입니다.

 

 

 이제 튜링 머신 HN을 이용해 해당 튜링 머신 HN이 무한 루프에 빠질 것인지에 대해 판별해 보겠습니다. 만약 튜링 머신 HN이 무한 루프에 빠질 것이라고 판단한다면 HN은 정지할 것입니다. 또한 무한 루프에 빠지지 않을 것이라고 판단한다면 무한 루프에 빠질 것입니다. 이는 모순입니다. 튜링 머신 HN은 HN이 무한 루프에 빠지지 않을 것이라고 판단한다면, 무한 루프에 빠지지 말아야 합니다. 하지만 튜링머신 HN은 이와 반대되는 결과를 내놓습니다. 이것이 바로 튜링 정지 문제입니다.

 

 

 이러한 튜링 정지 문제를 통해 알 수 있는 중요한 사실 중 하나는 바로 튜링 완전한 기계가 무한 루프에 빠질지 아니면 정상 수행하여 종료될지 판별할 수 있는 방법은 없다는 것입니다. 예를 들어, 전체 연산을 수행하는데 1시간이 걸리는 반복문이 존재할 경우, 개발자는 해당 루프가 무한 루프인지 아니면 언젠가 종료될 것인지 판별할 수 없습니다. 따라서 이 경우 개발자는 반복문이 종료될 것이라고 믿으면서 계속 기다리거나, 코드에 이상이 있다고 판단하여 강제 종료시킬 수밖에 없습니다.

 

III. 블록체인에서의 튜링 완전과 불완전

 지금까지 알아본 바에 따르면 개발자는 어떤 코드가 무한 루프에 빠질지, 아니면 어느 순간 정지할지에 대해 완벽하게 알 수 없습니다. 이는 블록체인에 있어서 심각한 문제를 발생시킬 수 있습니다.

 

 예를 들어 범용 블록체인 A가 있다고 가정해 보겠습니다. A는 블록체인을 컴퓨터 메모리처럼 사용합니다. 따라서 A 블록체인 네트워크의 참여자들은 트랜잭션을 읽고 해당 트랜잭션에 적힌 내용을 수행한 뒤, 결과 값을 반환하여 트랜잭션에 저장하여 완성한 후, 블록에 담아 연결하여 블록체인을 유지할 것입니다.

 

 

 이 상황에서 만약 누군가가 의도했든 의도치 않았든 무한루프에 빠질 가능성이 있는 코드가 포함된 트랜잭션을 전송한다면 어떻게 될까요? 튜링 정지 문제에 의해 블록체인 A의 네트워크 참여자들은 해당 트랜잭션에 적힌 코드를 수행할 경우 무한루프에 빠질지에 대해 판별할 수 없습니다. 따라서 참여자들은 무한루프가 포함된 트랜잭션을 수행하게 되고, 블록체인의 블록 생성은 멈춰버릴 것입니다.

 

 

 만약 단일 서버에서 이러한 문제가 발생할 경우, 시스템을 재가동하면 됩니다. 하지만 블록체인은 P2P 네트워크입니다. 전체 네트워크를 쉽게 끄거나 켤 수 없습니다. 즉, 이러한 상황이 발생할 경우 블록체인 네트워크는 치명상을 입게 됩니다.

 

 이러한 문제 때문에 비트코인 네트워크는 범용성을 포기하고 튜링 불완전을 선택하였습니다. 즉, 비트코인 네트워크는 반복문 등 일반적인 프로그래밍 언어가 갖춰야 할 것들을 포기했습니다.

 

 하지만 이더리움은 이러한 문제에도 불구하고 튜링 완전을 선택했습니다. 그렇다면 이더리움은 튜링 완전에서 발생할 수 있는 문제를 어떻게 해결했을까요? 이 부분에 대해서는 다음 글에서 알아보겠습니다.

 

 감사합니다.

 

 

다음글

[이더리움과 월드 컴퓨터] 1-3. 가스와 이더