[독자투고] 형식논리학 시리즈 3부: 튜링기계와 계획경제

형식 논리학 시리즈는 웹진 반란 독자분께서 기고해주신 글 입니다. 반란을 더욱 풍성하게 해주신 노고에 감사드립니다. 아울러 반란은 항상 독자 여러분의 투고를 환영하오니 이메일 통해서 연락해주시면 감사하겠습니다.

본 기고문은 경제 계산 문제를 튜링기계 개념을 통해 고찰함으로써 계획경제를 지지하고자 한다. 다만 사용하는 모형과 현실이 상당히 괴리가 있어서 달라서 계획경제에 대한 약한 근거만 될 수 있다. 여기서 모형화된 시장은 매우 이상화된 시장이고, 시장평형을 구하는 것이 현실에서의 계획경제의 목표가 되어야 하는지는 불명확하고, 경제 계획 과정 또한 매우 이상화된 것이다. 그러나 이상적인 모형에서조차 계획경제가 가능하지 않거나 효과적이지 않다면, 현실에서도 가능하지 않을 것이라고 생각하는 것이 타당하다는 사람들이 많으므로 적어도 이상적인 모형에서는 가능하다는 것을 보이는 본 작업은 의미가 있다.

먼저, 튜링기계와 컴퓨터과학적 복잡성에 대한 개념을 살펴보자. 튜링기계는 컴퓨터의 추상화된 모형이다[1]. 튜링기계 입장에서 문제들은 해결하는 데 걸리는 시간이 문제의 크기에 따라 어떤 식으로 증가하는지에 따라 복잡성의 층위가 나뉜다. 특정 조건을 만족하는 대상이 존재함이 보증되어 있었을 때, 그 대상을 찾는 문제들로 논의를 국한하자. 답이 존재하고 그것을 검증하는 데 걸리는 시간이 다항식 시간인 문제들을 TFNP 복잡도 문제라고 한다[2]. TFNP 복잡도 문제 중 일부 문제들은 다항식 시간에 문제를 푸는 방법이 있다. 이를테면 문제 크기가 n일 때, 문제를 풀려면 n⁴ 시간이 걸린다. 이러한 문제들을 FP 복잡도 문제라고 한다. 본 기고문에서 엄밀한 정의를 제시하진 않겠으나, TNFP 복잡도 문제 중 FP 복잡도 문제에 속하지 않는다고 엄밀하게 증명되지는 않았지만 거의 확실히 속하지 않는다고 믿어지는 PPAD-complete 복잡도 문제가 있다. 실용적으로는, FP 복잡도 문제여야 현실적인 시간 내에서 문제를 푸는 것이 가능하므로, PPAD-complete 문제를 정확히 푸는 것은 실용적이지 못하다.

이상적인 조건에서의 시장 경제에 대한 모형으로 Arrow-Debreu 모형[3]이 있는데, 여기서 시장 경제의 평형상태를 계산하는 문제의 복잡도를 계산해보면 선형의 효용함수를 가정하는 등 심각한 제약을 가하지 않는 한 튜링기계 관점에서는 적어도 PPAD-complete 등급이다[4][5]. 따라서 정확한 답을 계산하는 것은 실용적으로 불가능하다. 중앙에서 튜링기계 하나가 이를 계산하던, 여러 튜링기계가 분산되어 이를 계산하던, 결국엔 같은 하나의 튜링기계로 추상화할 수 있기 때문에 상관 없다.

참고로, 시장경제의 작동 역시 정확한 해를 구하는 것이 아니라 해당 해에 근사하게 수렴하는 것이다. 따라서, 근사해를 구하는 것이 현실적이다. 근사해를 구하는 빠른 알고리즘이 밝혀져 있다. [6] 중앙계획자가 해당 알고리즘을 따른다면, 시장평형에 대한 근사해를 구할 수 있을 것이다. 따라서 계획경제가 시장경제보다 시장평형의 근사해를 계산하는 데 열등하지 않고 오히려 시장이 평형에 근사적으로 도달하는 느린 과정보다 빠르게 시장평형을 근사적으로 계산해낼 수 있으므로 효율적이라고 주장할 수 있으나, 정보 분산의 문제라는 치명적인 문제가 있다.

정보 분산의 문제란 정보가 각 주체에 분산되어 있어서 시장경제와 다르게 중앙계획경제는 이를 즉각 반영하지 못할 수 있다는 비판이다[7]. 따라서 분산정보 문제를 해결하기 위해, 분산계획경제가 필요하다. 분산계획경제의 가능성은 인도 케랄라주 [8], 스페인 내전기 카탈로니아[9]가 보여준 바 있다. 해당 시도가 성공했는지 평가하는 것은 필자의 역량 밖이라 본 기고문에서 다루지 못하였으나, 해당 작업에 대해 역량이 있는 이들이 시도해 보면 좋다고 생각한다. 이론적 측면에서는 분산계획경제에 대한 구체적인 수학적 모형화 및 효과성 증명이 과제로 남는다고 생각한다.

[1] Paul M.B.Vitányi, Turing Machines and Understanding Computational Complexity, ArXiv, arXiv:1201.1223v1 [cs.CC] 05 Jan 2012

[2] Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, Volume 48, Issue 3, 1994, Pages 498-532,

[3] Arrow, K. J., & Debreu, G. (1954). Existence of an Equilibrium for a Competitive Economy. Econometrica, 22(3), 265–290.

[4] K. Jain, "A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities," in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 286-294,;

[5] X. Chen, D. Dai, Y. Du and S. -H. Teng, "Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities," 2009 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, USA, 2009, pp. 273-282

[6] Fleischer, L., Garg, R., Kapoor, S., Khandekar, R., Saberi, A. (2008). A Fast and Simple Algorithm for Computing Market Equilibria. In: Papadimitriou, C., Zhang, S. (eds) Internet and Network Economics. WINE 2008. Lecture Notes in Computer Science, vol 5385. Springer, Berlin, Heidelberg.

[7] Hayek, The Use of Knowledge in Society. The American Economic Review No.4 (Vol. XXXV September 1945), pp.519–30.

[8] Bharathy, M. (2025). Democratizing inclusive planning: insights from the people’s plan campaign in Kerala, India. Critical Policy Studies, 19(4), 722–741.

[9] Diedre Hogan, Industrial Collectivization During the Spanish Revolution, Red & Black Revolution (no 7, Winter 2003)