【イーサリアム】 チューリング完全性について調べてみた。

仮想通貨の１つであるイーサリアムについて調べていると、チューリング完全性（Turing complete）という言葉が出てきました。

チューリング完全性について全然知らなかったので、今回はイーサリアムにおけるチューリング完全性について調べてみました。

チューリング完全性とは？

チューリング完全性とは、イギリスの数学者の「アラン・チューリング」により定義されました。

同じ仮想通貨でも、ビットコインはチューリング完全性ではなく、イーサリアムはチューリング完全性だといわれます。

ではチューリング完全性とはどういうことなのでしょうか？

簡単にいうと、チューリング完全性とは、「どのような複雑なプログラムであっても計算（シュミレート）できる状態のこと」をいいます。

アラン・チューリングによると、「チューリングマシンをシュミレートするために使うことができるシステム」をチューリング完全と定義しました。このようなシステムを「万能チューリングマシン（UTM：Universal Turing machine）」といいます。

なので、Python や C言語などのプログラミング言語はチューリング完全であるといえます。

さらに、チューリングは、「あるプログラムが最終的に停止するかどうかは実行してみないと分からない」ということを証明しました。これを「停止性問題」といいます。

例えば、プログラムで「無限ループ」を実行すれば、そのプログラムは永久に停止しません。しかし、プログラムを実行しなければ、そのプログラムが「無限ループ」に陥ることは分からないということです。

プログラム実行前に本当に停止するか予測することはできないということです。

イーサリアムにおけるチューリング完全

イーサリアムでは、「イーサリアム仮想マシン（EVM）」と呼ばれる状態マシーンにより、プログラムを実行できるため、チューリング完全であるといえます。

イーサリアムでは、ブロックチェーン上でどのようなアルゴリズムのプログラムも実行できてしまいます。

一方、ビットコインでは、ブロックチェーン上で通貨の所有権の移動しか実行することができません。

イーサリアムは自由度が高く、契約やゲーム（スマートコントラクト）をブロックチェーン上で実行することができます。イーサリアムが革新的だといわれる理由がここにあります。

イーサリアムでは、EVM 上でスマートコントラクトを実行するのですが、上で書いた「停止性問題」が問題になってきます。

イーサリアムは、スマートコントラクトを実行してみないと、どれくらいメモリなどのリソースを使うかわかりません。

なので、もし、スマートコントラクトを実行して「無限ループ」などの状態が発生し、それがブロックチェーン上で起きてしまうと、かなりのリソースの無駄が出てしまいます。

それを防止するために、イーサリアムでは、ガス（gas）というものを使っています。

EVM がスマートコントラクトを実行するためにガスが必要で、処理コストに応じてガス量が多く使われる仕組みになります。

なので、無限ループに陥った場合、処理コストが増え、ガス量が足りなくなり EVM がスマートコントラクトの実行を停止するように設計されています。

参考文献