ルール110関数を作った

2024年4月8日 02:15

ルール110関数を作りました。

ルール110って何？

ルール110とは、セルオートマトンの一種です。

セルオートマトンは、全ての数に、その数の隣接する数を繋げた値によって、次の世代の数が変わります。

その数が変わるルールの一つが、ルール110です。ルール110では、

{その数の左の数,その数,その数の右の数}

が

{1,1,1}の時0、
{1,1,0}の時1、
{1,0,1}の時1、
{1,0,0}の時0、
{0,1,1}の時1、
{0,1,0}の時1、
{0,0,1}の時1、
{0,0,0}の時0

になります。(端っこには無限に0が広がっていることになっています。)

例えば、0011の次の世代は0111になり、111100001の次の世代は100100011になります。

可視化するとこんな感じです。

これはチューリング完全であることが知られています。チューリング完全は僕もよくわかっていませんが、入力と出力を工夫したらほとんどのプログラミング言語と同じことができるって考えて大丈夫です。

また、チューリング完全であるものを実行できるものも、自明ではあるかもしれませんが、チューリング完全です。

つまり、チューリング完全であるルール110を実装できるものはチューリング完全であるので、今回作った関数はチューリング完全であるであることが分かります。

ここまでだらだら書いていましたが、要約すると、凄い関数を作ったんだぞっていう自慢です。

デスモスっていうやつで、関数を作りました。グラフ計算機なんですが、機能性が高い関数電卓としても使用できます。
今回作った関数は下から見れます。

全体像はこんな感じです。

ちなみにこの関数はさっきのGIFとは違って、右から処理しています。

それでは、関数をひとつづつ解説していきます。

これはsの右からk番目の数を返します。

mod(s,10^k)は、右からk+1番目までの数で、例えばs=7685,k=2の時、85です。
mod(s,10^(k-1))は、右からk番目の数で、s=7685,k=2の時、5です。
この二つの差を求めることで、60が手に入り、それを下の10で割ることで、右から2番目の8が求められます。

この関数はsの桁数を求めます。logがめっちゃ使える。

これはルール110のやつです（語彙力(ほとんどの（語彙力）は大体は実際に足りないのは説明力だけど、この場合は本当に語彙力が足りない。)）。

c(1,1,0)を入れると1を返し、c(1,0,0)を入れると0を返します。

(l*|m-n|)の部分で赤いところを動かして、(1-l)(1-((1-|m-n|)(1-n)))の(1-l)で緑色のところ、(1-|m-n|)(1-n)で青を反転させて、それを1から引いて、正しくしています。

ここでさっきの関数を使って、重要な処理をしています。

f(s)から(バグが起きるので)10倍して渡されているので、シグマはn=2から始まっています。最後の*10^(n-2)で、桁数を調節して、n-1番目に処理した数字を入れています。

こんな感じで組み合わせることで、ルール110を実装しています。

desmosは完全チューリングです！！！！！

凄かったらいいねしてね