Power Apps がチューリング完全であることを示す | cloud.config Tech Blog

この記事は FIXER Advent Calendar 2021(https://adventar.org/calendars/6788) ３日目の記事です。

前回は本田君の「【人工衛星】Azure Orbitalが便利!?詳しく解説してみた! 」でした！

人工衛星を購入できない僕たちでも楽しめる良記事でしたね！！！！！

今回は本カレンダー初日で消えたと言われていたアプリを使った記事になります。

はじめに

みなさんは「計算可能性理論」という分野をご存じでしょうか。

一言でいうと「その装置がどんな問題を解くことができるか」ということについて考える学問です。

（そんなことして何がうれしいとかことは一旦置いておきます。）

世の中の多くのプログラミング言語は「チューリング完全」であるとされています。

「Aがチューリング完全である」とは「Aは万能チューリングマシンと同等の計算能力を持つ」という意味になります。

（何言ってんだって思われるかもしれませんが、そういう基準があるらしいということだけ覚えてください。）

みんな大好きC#や、果てにはMinecraftなんかもチューリング完全であるとされています。

ここで、我らが Power Apps もチューリング完全であるということを証明したいと思います。

チューリング完全であることを証明するには、既にチューリング完全であることが証明されているものを再現する方法がメジャーです。

そこで、今回はプログラミング言語の一つであるBrainf*ckをPowerApps上で再現します。

Brainf*ck(BF)

BFでは実行できる命令が8種類しかありません。

〇命令リスト

>：ポインタの見る番地を1増加
<：ポインタの見る番地を1減少
+：ポインタが指す値を1増加
-：ポインタが指す値を1減少
. ：ポインタが指す値を出力
, ：入力をポインタが指す値に書き込み
[ ：ポインタが指す値が0なら]の直後にジャンプする
] ：ポインタが指す値が0でないなら[の直後にジャンプする

また、必要な要素も6種類で済みます

〇BFを構成する要素

BFのプログラミングソース
ソースのどこを読んでいるか（ヘッド）
メモリ
メモリのどこを見ているか（ポインタ）
入力
出力

それでは早速作っていきましょう。

Power Apps でBFを再現する！

プログラムを入力する！

入力されたBFプログラムのソースは後の作業で使いやすいように一文字ずつ分割してコレクションに格納していきます。

ForAll(
    Sequence(Len(ソース入力ボックス.Text)) As i,
    Collect(
        ソース,
        {
            Index: CountRows(ソース),
            Value: Mid(
                ソース入力ボックス.Text,
                i.Value,
                1
            )
        }
    )
);
Reset(ソース入力ボックス)

プログラミングソースの１文字目に振られるIndexは0になります。

プログラムを処理する！

実行ボタンを押して処理ページへ遷移します。

値の初期化などはページのOnVisibleで行います。

UpdateContext({
    ヘッド:0,
    ポインタ:0,
    アウトプット:""
});
ClearCollect(メモリ,{Index:0,Value:0});

続いて、実際の処理はタイマーコンポーネントのOnTimerEndに書きます。

これにより1ステップごとに進んでいく過程をみることができます。

Switch(
    LookUp(
        ソース,
        Index = ヘッド
    ).Value,
    ">",
    If(
        CountRows(メモリ) = ポインタ + 1,
        Collect(
            メモリ,
            {
                Index: CountRows(メモリ),
                Value: 0
            }
        )
    );
    UpdateContext({ポインタ: ポインタ + 1}),
    "<",
    UpdateContext({ポインタ: ポインタ - 1}),
    "+",
    Patch(
        メモリ,
        LookUp(
            メモリ,
            Index = ポインタ
        ),
        {
            Value: LookUp(
                メモリ,
                Index = ポインタ
            ).Value + 1
        }
    ),
    "-",
    Patch(
        メモリ,
        LookUp(
            メモリ,
            Index = ポインタ
        ),
        {
            Value: LookUp(
                メモリ,
                Index = ポインタ
            ).Value - 1
        }
    ),
    ".",
    UpdateContext(
        {
            アウトプット: アウトプット & Char(
                LookUp(
                    メモリ,
                    Index = ポインタ
                ).Value
            )
        }
    ),
    "[",
    If(LookUp(メモリ,Index=ポインタ).Value=0,
    UpdateContext({ヘッド:LookUp(ソース,Value="]" And Index>ヘッド).Index})
    ),
    "]",
    If(LookUp(メモリ,Index=ポインタ).Value<>0,
    UpdateContext({ヘッド:Last(Filter(ソース,Value="[" And Index<ヘッド)).Index})
    )
);
UpdateContext({ヘッド: ヘッド + 1})

最後に、ソースとメモリのどこが今処理されてるのか視覚的にわかるようにします。

If(ThisItem.Index=ヘッド,
RGBA(150, 150, 255, 0.5),
RGBA(0, 0, 0, 0)
)

If(ThisItem.Index=ポインタ,
RGBA(150, 150, 255, 0.5),
RGBA(0, 0, 0, 0)
)

まとめ

無事にPower Apps上で BFを再現することができました。

よってPower Apps はチューリング完全であるということが証明できました□

※妥協ポイント

入力を受け取る処理を省略しました
- 「,」を読んだタイミングでタイマーを一度止め、入力を受け付けたタイミングで再開すれば実装可能です
- 尺の都合でカットしました
ループのネストに対応していません
- Filterとかを頑張れば実現可能だと思われます