チューリング・マシンでのプログラミング

10/15の「楽しい数学：計算理論入門」http://mathnight3.peatix.com/　の準備で、チューリング・マシンでのプログラミングの練習をしているのだが、なかなか苦戦している。

カウンターもスタックもないし、「状態」の数をできるだけ減らそうとすると、いろいろ難しい。（でも、パズルみたいで面白い。）

・ E((()))()(())E といった、EとEとの間の括弧がバランスが取れているかをチェックせよ。（失敗）

右に進んで最初の右括弧')'を探して、他の文字'X'に置き換え、今度は左に進んで、左括弧'('を探して、それも'X'に置き換えて、また右括弧')'を探すの繰り返せばいい。状態は「右」と「左」の二つで十分。うまくいけば右のEに到達し、まずければ左のEに落ちる。

と思ったのだが、これだと、明らかにバランスが取れていない、例えば、E((((Eも、右のEに届いてしまう。右のEに届いたら、もう一度チェックが必要。状態「Check」を使えばできるのだけれど、なんとか二つの状態でできないか、思案中。

・0と1からなる文字列の長さを計算せよ。（できた！でも、ずるい）

左から右に進んで、現れる0を全部1に置き換える。これでいい。ただし、長さは、1進数。nは、n個の1で表すことにすればいい。

・自然数 m,n のかけ算を行え。（なんとかできるかも）

これも1進数で考えれば、m個の1を、n回、右のほうにコピーしてやればいい。

まず、コピーの処理を考えたのだが（図）、状態が7つもあって気にくわない。それに、1進法のかけ算のためだけなら、0のコピーは考える必要はないしね。

問題は、「n回」コピーの部分。データ構造（というかテープの構造、工夫しないと）

・1進数を2進数に変換せよ。

これは、大昔、どっかでやり方を見た気がする。ちょっとスマートな方法があったはず。ググろう。

問題は、あと10日で、「万能チューリングマシン」にたどり着くことができるかということ。

ガンバリマス。