チューリング マシン (状態と明示的なデルタ関数を使用する昔ながらの方法) の設計を依頼されました。要件は次のとおりです。入力は TM が停止するイプシロン (無限の数の「空白」記号)、使用されるアルファベットは {B, 0, 1} (B は「空白」記号)、および状態の最大数です。は 5 です。
目標は、できるだけ多くの "1" を出力するソリューションを見つけることです。
私の考え：最初に2つの「0」（2つの状態から取得できる最大値）を出力し、次にすべての0を「1」に置き換えて、別の「1」を文字列に追加します。「B」に達した場合は、これも交換してください。
合計 6 個の "1" が出力されます。
多分誰かがもっと手に入れる方法を思いつきましたか？
追加
さて、クレジットはこのヒントのZaneに送られます.
いくつかのグーグル検索とウィキペディアの読みによると、これはまさに私が/私が探していたものです: http://www.logique.jussieu.fr/~michel/ha.html#tm43