ADD_STATE(A); ADD_STATE(B); ADD_STATE(C); ADD_STATE(D); ADD_RULE(A, Blank, 1, Right, B); ADD_RULE(A, 1, 1, Left, B); ADD_RULE(B, Blank, 1, Left, A); ADD_RULE(B, 1, Blank, Left, C); ADD_RULE(C, Blank, 1, Right, Stop); ADD_RULE(C, 1, 1, Left, D); ADD_RULE(D, Blank, 1, Right, D); ADD_RULE(D, 1, Blank, Right, A); using tape = Tape<Blank>; using machine = Machine<A, 0, tape>; using result = Run<machine>::type; int main() { print(result()); return 0; }
出力では、予想どおり、次のようになります
1 _ 1 1 1 1 1 1 1 1 1 1 1 1
ここでコードを見ることができます： https : //ideone.com/MvBU3Z あなたがすべてが内部に配置されている方法を知りたい場合は、猫へようこそ。
チューリングマシンを完全に動作させるには（さらにMT）、次のものが必要です。
1.シンボル付きのリボン
2.文字をテープに読み書きする方法
3.テープをナビゲートし、必要に応じて拡張する方法
4.状態と遷移規則のシステム
5.システム全体の次の状態を計算する方法（マシン+テープ）
6.マシンが最終状態に達したときに実行を停止する方法
すべての操作は、通常の生活のように変数ではなく、型と定数式で実行する必要があります。 標準C ++ライブラリとの一貫性を保つために、次の計算方法を使用します。
// template<class> class Operation; // template<class Input> class Operation { public: // , using type = typename Output; }
結果を保存するために「type」という名前を使用すると、std ::条件付きおよびstd :: Integral_constantを使用した便利なトリックが可能になります。これについては後で説明します。
1. MTは有限のアルファベットを使用するため、テープ上の記号は整数で表されると一般性を失うことなく想定できます。 デフォルトでは、テープには-1に等しい定数Blankで指定された文字が含まれていることに同意します。 必要に応じて、この値は簡単に変更できます。
constexpr int Blank = -1; template<int... xs> class Tape { public: using type = Tape<xs...>; constexpr static int length = sizeof...(xs); };
テープで何ができますか？ たとえば、画面に表示することができます。 印刷機能は、通常の意味で、マシンのプログラムで使用される唯一の機能です。
template<class T> void print(T); template<> void print(Tape<>) { std::cout << std::endl; } template<int x, int... xs> void print(Tape<x, xs...>) { if (x == Blank) { std::cout << "_ "; } else { std::cout << x << " "; } print(Tape<xs...>()); }
再帰的なパターンを持つ標準のトリックを使用します。 ここで、結果のコードを見ることができます： https : //ideone.com/DBHSC6
2.読み取りと書き込みに進む前に、いくつかの補助操作を行う必要があります。
template<class, class> class Concatenate; template<int... xs, int... ys> class Concatenate<Tape<xs...>, Tape<ys...>> { public: using type = Tape<xs..., ys...>; };
連結は簡単です。
template<class> class Invert; template<> class Invert<Tape<>> { public: using type = Tape<>; }; template<int x, int... xs> class Invert<Tape<x, xs...>> { public: using type = typename Concatenate< typename Invert<Tape<xs...>>::type, Tape<x> >::type; };
反転はもう少し複雑です。最初の文字を取得し、それを最後に転送して、裏返した状態で連結します。 内部では、再帰が展開され、その結果、必要なものが得られます。 実行例を次に示します。https ： //ideone.com/47GKNp
文字を読むことは、魔法が標準ライブラリから始まる場所です。
template<int, class> class Read; template<int n, int x, int... xs> class Read<n, Tape<x, xs...>> { public: using type = typename std::conditional< (n == 0), std::integral_constant<int, x>, Read<n - 1, Tape<xs...>> >::type::type; };
ロジックは実際には比較的単純です。n== 0の場合、std :: Integral_constantでラップされたテープの最初の文字を返します。それ以外の場合は、nを1つ減らして最初の文字を破棄します。 :: type :: typeの構成は何ですか？ 最初のタイプは、std ::条件を参照します。 std ::条件付き<T、A、B> :: T == trueの場合、タイプはAに等しく、その他の場合はBに等しくなります。 したがって、nの値に応じて、構築全体が次の式のいずれかに展開されます。
using type = std::integral_constant<int, x>::type; using type = Read<n - 1, Tape<xs...>>::type;
最初の行はtype = std :: Integral_constant <int、x>と同等です。2行目は再帰を引き起こします。 しかし、次のようにこのコードを書くことが不可能だった理由：
template<int n, int x, int... xs> class Read<n, Tape<x, xs...>> { public: using type = typename std::conditional< (n == 0), std::integral_constant<int, x>, typename Read<n - 1, Tape<xs...>>::type >::type; };
答え：最初のケースでは、テンプレートRead <n-1、Tape <xs ... >>はnの値に応じてインスタンス化されます。2番目のケースでは、内部エイリアス（::タイプ）を明示的に使用するため、常にインスタンス化されます。 テンプレートの名前に言及しただけでは、インスタンス化されません。内部の1つを使用しようとすると、テンプレートがインスタンス化されます。 したがって、2番目の例の式は無限再帰につながり、それでも停止しますが、エラーが発生します。 これは:: typeで受け入れられます:: typeは今後積極的に使用されます。
ここでは、テープからの読み取りの例を見ることができます： https : //ideone.com/vEyASt
記録。 xではなくyを書きたいとします。 書き込み操作は、テープ全体をxの前の部分、シンボルx自体、xの後の部分に分割し、xをyに置き換え、すべての部分を連結して全体に戻すことで表すことができます。 最初と最後のn個の文字を計算する操作を定義します。
template<int, class> class NLast; template<int n, int x, int... xs> class NLast<n, Tape<x, xs...>> { public: using type = typename std::conditional< (n == sizeof...(xs)), Tape<xs...>, NLast<n, Tape<xs...>> >::type::type; }; template<int, class> class NFirst; template<int n, int... xs> class NFirst<n, Tape<xs...>> { public: using type = typename Invert< typename NLast< n, typename Invert<Tape<xs...>>::type >::type >::type; };
最後のn文字を取得するには、読み取りの場合とほぼ同じように行います。残りの部分の長さがnに等しくなるまで、一度に1文字ずつテープを短くします。 最初のn文字を取得するには、テープを裏返し、最後のn文字を取り、結果を裏返します。 使用例： https : //ideone.com/igYF3W
最後に、直接エントリ：
template<int, int, class> class Write; template<int pos, int x, int... xs> class Write<pos, x, Tape<xs...>> { public: using type = typename Concatenate< typename Concatenate< typename NFirst<pos, Tape<xs...>>::type, Tape<x> >::type, typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type >::type; };
このコードを理解するのは難しくありません。実際に何が起こっているかを知っています。 記録例： https : //ideone.com/w2mUdh
現時点では、テープを表すためのクラスがあり、文字を読み書きすることもできます。 次に、テープの移動方法を学習する必要があります。
3. MTは、ホールド、左、右の移動操作をサポートします。 それらのそれぞれは、テープの次の位置と次の状態を計算し、テープの現在の状態と位置を知ることができなければなりません。 車が位置0のシンボルを見ていて、それを左に移動したい場合、テープを拡張する必要があります。 同様に、車が最後のキャラクターを見て右に移動する場合。
template<int, class> class Hold; template<int pos, int... xs> class Hold<pos, Tape<xs...>> { public: constexpr static int position = pos; using tape = Tape<xs...>; }; template<int, class> class Left; template<int pos, int... xs> class Left<pos, Tape<xs...>> { public: constexpr static int position = typename std::conditional< (pos > 0), std::integral_constant<int, pos - 1>, std::integral_constant<int, 0> >::type(); using tape = typename std::conditional< (pos > 0), Tape<xs...>, Tape<Blank, xs...> >::type; }; template<int, class> class Right; template<int pos, int... xs> class Right<pos, Tape<xs...>> { public: constexpr static int position = pos + 1; using tape = typename std::conditional< (pos < sizeof...(xs) - 1), Tape<xs...>, Tape<xs..., Blank> >::type; };
例： https : //ideone.com/m5OTaT
4.これで、状態に移動できます。 マシンが何らかの状態にあり、テープからシンボルを読み取る場合、3つのことを知っておく必要があります。何を書き込むか、どこに移動するか、どの状態に進むかです。 状態をテンプレート特殊化のグループとしてプログラムすることが決定されました。各特殊化はペア（状態、シンボル）、つまり遷移規則に対応します。 次のルールを設定するとします。状態Aにあり、シンボル0を読み取り、代わりに1を書き込み、右に移動して状態Bに移動する必要があります。このルールは次のようになります。
template<> class A<0> { public: constexpr static int write = 1; template<int pos, class tape> using move = Right<pos, tape>; template<int x> using next = B<x>; };
ここでは、最新のC ++の優れた機能であるエイリアステンプレートを使用しています。 「移動」フィールドと「次の」フィールドは単なるタイプではなく、タイプテンプレートであり、将来はMTが次の状態を計算するために使用されます。 各ルールに対してこのような構成を記述するのはかなり面倒なので、マクロに移行するタスクをまとめます。 マシンが停止する必要がある状態は、停止と呼ばれます。
5.システム全体の状態（マシンの状態、その現在の位置、およびテープの状態）を保持するために、クラスMachineを定義します。 このクラスでできることは、シミュレーションの1ステップを実行し、次の状態を計算することだけです。
template<template<int> class State, int pos, int... xs> class Machine<State, pos, Tape<xs...>> { constexpr static int symbol = typename Read<pos, Tape<xs...>>::type(); using state = State<symbol>; template<int x> using nextState = typename State<symbol>::template next<x>; using move = typename state::template move<pos, modifiedTape>; constexpr static int nextPos = move::position; using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type; using nextTape = typename move::tape; public: using step = Machine<nextState, nextPos, nextTape>; };
まず、テープからシンボルを読み取り、「シンボル」として保存します。 次に、特定の文字値でStateクラスをインスタンス化し、遷移ルールを取得します。 次のマシン条件は次のように定義されます。
template<int x> using nextState = typename State<symbol>::template next<x>;
「次」の前に「テンプレート」というキーワードが必要なのはなぜですか？ 標準に従って、この名前がスコープ演算子（ "::"）の後に使用される場合、埋め込みテンプレートの名前の前に「テンプレート」を記述する必要があります。 移動操作を計算するとき、同じ効果が観察できます。
テープの次の状態を計算するために、新しいシンボルをテープに書き込み、必要に応じて展開して、書き込み操作と移動操作を順番に呼び出します。 新しい位置の計算は明らかです。
最後に、すべての準備が整いました。システムの次の状態を計算して、手順を実行できます。 一時的な補助関数を作成して、マシンの状態を表示し、いくつかの簡単なプログラムを作成し、その実装を段階的に実行できます： https : //ideone.com/XuBDry この例では、マシンがどのように正しく移動し、パス内のすべてを置き換えるかを観察できます。
6.すべてが機能しているように見えますが、さらに深くする必要があります。プロセスへの入力は、マシンの初期状態、テープの位置と状態です。最後に、マシンが停止状態に達したときにテープに何が起こったかを知りたいです。 OK、クラスを書きましょう
template<class> class Run; template<template<int> class State, int pos, int... xs> class Run<Machine<State, pos, Tape<xs...>>> { using step = typename Machine<State, pos, Tape<xs...>>::step; public: using type = typename std::conditional< std::is_same<State<0>, Stop<0>>::value, Tape<xs...>, Run<step> >::type::type; };
停止条件を確認するために、マシンの現在の状態と値0の停止状態をインスタンス化し、その後、std :: is_sameを使用してそれらを互いに比較します。 それらが等しい場合、テープを返します。それ以外の場合、次のステップは行為であり、再び停止条件をチェックします。
それでは、何かを書いてみましょう。 たとえば、バイナリ形式で数字を増やします。 数字が紙のように左から右に書かれていると仮定します。
ADD_STATE(S0); ADD_STATE(S1); ADD_STATE(S2); ADD_RULE(S0, Blank, Blank, Left, S1); ADD_RULE(S0, 0, 0, Right, S0); ADD_RULE(S0, 1, 1, Right, S0); ADD_RULE(S1, Blank, 1, Right, S2); ADD_RULE(S1, 0, 1, Left, S2); ADD_RULE(S1, 1, 0, Left, S1); ADD_RULE(S2, Blank, Blank, Hold, Stop); ADD_RULE(S2, 0, 0, Right, S2); ADD_RULE(S2, 1, 1, Right, S2); using tape = Tape<Blank, 1, 1, 0, Blank>; using result = Run<Machine<S0, tape::length - 1, tape>>::type; int main() { print(tape()); print(result()); return 0; }
https://ideone.com/AgK4nx インクリメントを数回実行したい場合はどうしますか？ もちろん、別の操作クラスを作成して、それを数回呼び出します。すべてが単純です：
template<class> class Increment { }; template<int... xs> class Increment<Tape<xs...>> { public: using type = typename Run<Machine<S0, Tape<xs...>::length - 1, Tape<xs...>>>::type; }; using tape = Tape<Blank, 1, 1, 0, Blank>; int main() { print(tape()); print(Increment<tape>::type()); print(Increment<Increment<tape>::type>::type()); print(Increment<Increment<Increment<tape>::type>::type>::type()); print(Increment<Increment<Increment<Increment<tape>::type>::type>::type>::type()); print(Increment<Increment<Increment<Increment<Increment<tape>::type>::type>::type>::type>::type()); return 0; }
https://ideone.com/zPyu6B
この幸せなメモで、私は丸くさせてください。 githubへのリンク： https : //github.com/fnz/CTTM 、新しいプログラムでのプルリクエストは大歓迎です。