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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

参考文献

関連記事

【イーサリアム】 ホリエモンが2014年当時にイーサリアムの可能性に気付いていた!?

ホリエモンこと堀江氏が、2014年の自身のブログで「イーサリアムやべぇ。。。」というタイトル

記事を読む

【イーサリアム】日本円のチャートで比較する方法【イーサリアム・クラシック】

イーサリアム(Ethereum)は、2020年時点で、時価総額がビットコインに次ぐ第2位の仮

記事を読む

【仮想通貨】時価総額のランキングを円(JPY)で見る方法。

ビットコインやイーサリアムなどの仮想通貨の時価総額のランキングを 円(JPY)で見れる分かり

記事を読む

【ビットコイン】1ブロックに含まれる情報について調べてみた【マークル木】

ビットコインなどの仮想通貨では、トランザクション(取引)の束を「ブロック」という単位で扱い、

記事を読む

【イーサリアム】 公開鍵暗号について調べてみた。

仮想通貨の1つであるイーサリアムでは、公開鍵暗号という技術が使われています。 公開鍵暗

記事を読む

【仮想通貨】デジタル署名と公開鍵暗号の違いは!?

ビットコインなどの仮想通貨のブロックチェーン技術で用いられている「デジタル署名」「公開鍵暗号

記事を読む

【Solidity】 イーサリアムでコントラクトを生成してみた。

スマートコントラクトプログラミングの高級言語の1つである Solidity を使って、イーサ

記事を読む

【ビットコイン】ハッシュ関数(SHA-256・RIPEMD-160)について調べてみた。

ビットコインなどの仮想通貨で使用されているハッシュ関数(hash function)という技

記事を読む

【仮想通貨】トランザクションについて調べてみた【ブロックチェーン】

ビットコインなどの仮想通貨では、取引をトランザクションで記述されます。 そのトランザク

記事を読む

【MetaMask】イーサリアムのウォレットを使ってみた【テスト環境】

今回、イーサリアムのウォレットの1つである MetaMask(メタマスク)を使って、テストブ

記事を読む

【TensorFlow】GPUを認識しない時の対処方法【Python】

TensorFlow で GPU を認識させようとしたときにハマってし

【耳コピ】音楽ファイルを楽器ごとに分離する方法【Spleeter:フリー】

今回は、mp3 などの音楽ファイルをボーカル、ベース、ドラムなどの楽器

【Chainer】手書き数字認識をしてみた【Deep Learning】

Chainerを用いて、ニューラルネットワークを構築し、手書き数字認識

【Spyder】引数のあるスクリプトを実行する方法。

Python の統合開発環境(IDE)である Spyder では、簡単

【Anaconda】Prompt 上で Git コマンドを実行する方法。

Anaconda のコマンドプロンプト(Anaconda Prompt

→もっと見る

PAGE TOP ↑