[TIL - 20240703] Turing complete란?

Turing complete(or Computationally universal)?

Turing complete는 충분한 time과 resource가 주어진다면 복잡해도 computational problem이든 해결할 수 있다는 의미이다. (엄격하게로는 무한한 storage capacity가 필요) Turing complete에 대해 잘 알려진 예시는 Python이다. Python은 단순한 계산으로 복잡한 AI task와 같은 문제를 해결한다. 또는 Scratch라는 Programming language가 있다. (Scratch는 어떻게 코드를 작성하는지 아이들에게 가르칠 때 종종 사용한다)

• minimum set of features
  
  • flow of control conditional on data (조건문을 표현할 수 있어야 함)
  • a jump back to an earlier point in the program, on top of which you could implement a loop (loop와 같이 초기 point로 돌아갈 수 있어야 함. 같은 맥락에서 BPF는 backwards jump를 금지하기 때문에 Turing complete가 아님)
  • some storage that is both readable and writable and arbitratily large (큰 스토리지가 필요함. 계산하는 데 제한이 되지 않아야 하며 많은 옵션들이 필요함. memory addressed by pointers, arrays, stacks, cons cells, pure data structure, etc.)

즉, Turing complete는 무한한 스토리지와 시간이 있다는 가정 하에 어떤 복잡한 연산이나 문제든 해결할 수 있다는 의미이다. General-purpose computer에서 최소한의 feature는 조건문, 반복문, 읽고 쓸 수 있는 큰 스토리지(complex structure)가 필요하다.

 

Blockchain & limitations

Ethereum은 Turing complete를 사용한 최초의 blockchain platform이다. 하지만 여전히 critical risk가 존재한다.

• Security Vulenerabilities : Turing complete한 언어나 smart constract는 복잡하며, 이로 인해 버그, 취약성, 그리고 unintended behaviours가 발생할 수 있다. 이런 취약점을 악용할 수 있는 가능성이 있다.
• Inefficiency and Scalability challenges : slower transaction processing, higher costs, and scalability limitations
• Lack of Predictability : due to the halting problem (Gödel의 불완전성 정리) → 수학적 형식 쳬계가 완전하고 일관적이면서도 모든 참된 명제를 포함할 수 없음. 포함하려면 시스템이 자체적으로 모순에 빠질 수 있
• Difficulty in Upgrades and Maintenance : 업그레이드나 유지보수를 할 때, Turing complete 언어의 복잡성, 잠재적인 종속성, 이전 버전과의 호환성의 필요성으로 인해 더 복잡해진다.

 

Reference

- what does turing complete mean and what are some examples

https://www.owlift.com/blog/submission/what-does-turing-complete-mean-and-what-are-some-examples/

what does turing complete mean and what are some examples

 

- what is Turing complete?

https://www.bitstamp.net/learn/blockchain/what-is-turing-complete/

What is Turing complete? - Bitstamp Learn Center

 

- Is there a minimum set of features without which Turing Completeness is impossible?

https://stackoverflow.com/questions/449014/what-are-practical-guidelines-for-evaluating-a-languages-turing-completeness

What are practical guidelines for evaluating a language's "Turing Completeness"?

 

- What is Turing completeness?

https://www.lenovo.com/us/en/glossary/what-is-turing-completeness/?orgRef=https%253A%252F%252Fwww.google.com%252F

Exploring Turing Completeness | Lenovo US

 

- Turing completeness: Good or bad for blockchains? A ChatGPT perspective...

https://www.linkedin.com/pulse/turing-completeness-good-bad-chatgpt-perspective-daniel-liebau/

Turing completeness: Good or bad for blockchains? A ChatGPT perspective...