4

チューリング マシンの命令にコンパイルする独自のプログラミング言語を作成しましたが、実装方法を知りたいと思っていましたif(a>b) do _ end。言語の定義は次のとおりです（ここでも入手できます）

変数は任意の幅で動的に割り当てられるため、任意の大きな整数を持つことができます

各行は、関数の呼び出し (引数の変更)、while ループの開始 (実際には for ループに近い)、変数の割り当ての 3 つのうちのいずれかを実行できます。

使用可能な関数はincr、(1 ずつ増加、オーバーフロー可能)、decr(1 ずつ減少、オーバーフロー可能)、pop(変数から最後の桁を削除)、first(変数の最上位の 0 を 1 にfrost変更)、および (最も重要な桁を変更) です。有意な 1 からゼロ)。

while ループの構文は次のとおりです。

while a <func> {
    _
}

基本的にループするたびにエラー状態になるまで<func>行います。aエラー条件は次のとおりで、incrすべてfirst1 で、decrすべてfrost0 でpop、最後の桁を削除します。incrまたはを使用した while ループの後、frostループ変数のすべてのビットが 0 になり、 と が逆にfirstなりdecrます。while ループは関数呼び出しで終了する必要があり、各実行後に含まれるすべての変数を削除します。

割り当ては、構文に基づいていくつかの異なることを行うことができます。これよりも長い場合、変数が所有するスペースにa=b変数をコピーすることを意味し、作成された最新の変数でない限り、未定義の動作を引き起こします。左に 5 つのパディング ビット (ゼロに設定) を割り当てると、最後に変数が作成されない限り、オーバーフローによって未定義の動作が発生します。をゼロにします。最後に 3 ビットで代入します。babaaa=b,5baaa=a,0aa=5,35 % 2**3a

今私はで実装if(a != 0) do _ endすることができます

while a decr {
    _
    t=0,1
    while a incr {
        incr(t)
    }
    incr(t)
}

if(a==b)私の質問は、if(a!=b)、 、などの他の if ステートメントをどのように実装できるかです。if(a>b)

そして、二次的な質問として、この言語はチューリング完全です.この回答に基づいてそう信じていますプログラミング言語がチューリング完全であるための最小基準はありますか? . 言語が 1 ～ 5 を満たすことはわかっていますが、6 についてはわかりません。

4

1 に答える 1

0

(ループまたは incr/decr の動作について間違っていると仮定した場合はお知らせください。それによって私の答えが変わる可能性があります)

の元のコードはif(a!=0)永遠にループしているように見えます。そのままでは、while(a) do _ end無期限にループするか、まったくループしないため、実行しています。最後tに、ループの外には存在せず、キャプチャしようとしている値のように見えますが (比較では true/false)、ループ内で使用されているようには見えません。

コメント構文がないので、必要に応じて// comment/ c スタイルのコメントを挿入します。

たぶん、このようなもの...

もし (a > 0) do _ end

// if (a > 0) do _ end
_a = a
while _a decr {
    // overflow iif _a= 0
    _ // do something
    _a = 0
    frost( _a ) // only function calls at end of loops
}

if (a == 0) do _ end

// if (a == 0) do _ end
_a = a
result = 1,1
while _a decr {
    // overflow iif _a= 0
    _a = 0
    frost( result ) // only function calls at end of loops
}
while result decr {
    // overflow iif result = 0
    _ // do something
    frost( result ) // exit loop
}

お気づきのように、ゼロ以外のチェックのパターンは簡単です-デクリメントし、オーバーフロー（技術的にアンダーフロー）していない場合は、1以上のものを扱っています。トリックは を終了するwhileことです。これは、decr テストを使用し、終了時にテスト対象の変数を 0 に設定することで実行できます。ターゲット変数が 0 の場合は結果が変更されず、ターゲットが 1 の場合は in のように 0 になるため、このfrost関数は適していresultます。

ドキュメントには、関数は割り当てや別のループではなく、ループの終わりをマークする必要があると書かれていますが、独自の例はこれと矛盾しています。

残りのテスト条件の例を作成していa > bますa == b。他のものは、これら 2 つの論理反転 / not 演算子のみから導出できますresult。

もし (a == b) do _ end

// if( a == b ) do _ end
a_cond = a
b_cond = b
// step 1: a_cond = a - b
while b_cond decr {
    decr(a_cond)
}
// step 2: if (a_cond == 0)
result = 1,1
while a_cond decr {
    // overflow iif a_cond = 0
    a_cond = 0
    frost( result ) // only function calls at end of loops
}
while result decr {
    // overflow iif result = 0
    _ // do something
    frost( result ) // exit loop
}

もし (a > b) do _ end

仕掛品。(a==b) ケースと同様になります

于 2016-06-29T07:23:14.110 に答える