アカウント名:
パスワード:
変数を扱えて、条件判断とループができればOKだっけ?
「無限にメモリが増やせれば…」というのが絶対条件。現実世界の事物について「〇〇はチューリング完全」という場合、よく見ると「××が無限ならば」みたいな条件が必ずついている。C言語は安易にメモリを無限にすると言語仕様に違反してしまうので、工夫しないとチューリング完全にならないとかある。
元ネタはパンチカード(穿孔テープ)なんだから、別にメモリである必要はないだろ。C言語でパンチカードに入出力できたらそれで充分。
シリコン上のRAMである必要はないけど、無限に容量があって(シーケンシャルアクセスでもいいから)必要とあればどこまでも読みに戻れるという条件は必要。C言語の規格上、シーク可能なファイルのサイズは有限でなければならないのでそんな簡単じゃないんだな
C言語の仕様にパンチカード操作は用意されていないので、C言語に「無限に長いテープを操作できる仕組み」という条件を加えたらチューリング完全、という風に話を持って行かざるを得ないんじゃないかな。
で、それを加えるのは「無限メモリ」の但し書きを加えるのよりマシなのか? と言う話になる。
まあ、「標準入出力が無限テープエミュレータに繋いである環境」を想定すれば、C言語の仕様そのものは汚さずに済むからマシなのかな。
無限テープエミュレータは、"r"を渡すと現在位置の値がを返し、"w(値)"を渡すと現在位置を"値"に書き換え、"b"と"f"で進んだり戻ったり、というような想定で。どこまで進んだり戻ったりしても、何かしら上手いことやってくれるマジカルなプログラム。
テープはrでwでbなシーク可能のファイルハンドルで良いじゃん。まぁぶっちゃけ適当な配列とポインタないしインデックスで十分だけどね。実際問題無限のテープを現実に用意することは物理的にできないから、「物理的制約によりテープ長はNまでとする」てのは絶対に生じる。であればそのNに大した意味はなくテキトーな定数で良い。
実際問題ゲームワールド内でやる奴もエリアサイズやオブジェクト数の上限があるしね。
数学的には、任意のチューリングマシンをエミュレート出来れば、チューリング完全。チューリングマシンの仕様をデータ列の形で与えることで任意のチューリングマシンをエミュレート出来る、ユニバーサルチューリングマシンというのが有るので、それを実装できればチューリング完全、というのが話が早い。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
最初のバージョンは常に打ち捨てられる。
チューリング完全の条件って (スコア:0)
変数を扱えて、条件判断とループができればOKだっけ?
Re:チューリング完全の条件って (スコア:1)
言われてみればifとforだけあれば十分ですね
初代ポケモン黄もチューリング完全らしい
Re: (スコア:0)
「無限にメモリが増やせれば…」というのが絶対条件。現実世界の事物について「〇〇はチューリング完全」という場合、よく見ると「××が無限ならば」みたいな条件が必ずついている。C言語は安易にメモリを無限にすると言語仕様に違反してしまうので、工夫しないとチューリング完全にならないとかある。
Re: (スコア:0)
元ネタはパンチカード(穿孔テープ)なんだから、別にメモリである必要はないだろ。C言語でパンチカードに入出力できたらそれで充分。
Re: (スコア:0)
シリコン上のRAMである必要はないけど、無限に容量があって(シーケンシャルアクセスでもいいから)必要とあればどこまでも読みに戻れるという条件は必要。
C言語の規格上、シーク可能なファイルのサイズは有限でなければならないのでそんな簡単じゃないんだな
Re: (スコア:0)
C言語の仕様にパンチカード操作は用意されていないので、C言語に「無限に長いテープを操作できる仕組み」という条件を加えたらチューリング完全、という風に話を持って行かざるを得ないんじゃないかな。
で、それを加えるのは「無限メモリ」の但し書きを加えるのよりマシなのか? と言う話になる。
まあ、「標準入出力が無限テープエミュレータに繋いである環境」を想定すれば、C言語の仕様そのものは汚さずに済むからマシなのかな。
無限テープエミュレータは、"r"を渡すと現在位置の値がを返し、"w(値)"を渡すと現在位置を"値"に書き換え、"b"と"f"で進んだり戻ったり、というような想定で。どこまで進んだり戻ったりしても、何かしら上手いことやってくれるマジカルなプログラム。
Re: (スコア:0)
テープはrでwでbなシーク可能のファイルハンドルで良いじゃん。
まぁぶっちゃけ適当な配列とポインタないしインデックスで十分だけどね。
実際問題無限のテープを現実に用意することは物理的にできないから、
「物理的制約によりテープ長はNまでとする」てのは絶対に生じる。
であればそのNに大した意味はなくテキトーな定数で良い。
実際問題ゲームワールド内でやる奴もエリアサイズやオブジェクト数の上限があるしね。
Re: (スコア:0)
数学的には、任意のチューリングマシンをエミュレート出来れば、チューリング完全。
チューリングマシンの仕様をデータ列の形で与えることで任意のチューリングマシンをエミュレート出来る、ユニバーサルチューリングマシンというのが有るので、それを実装できればチューリング完全、というのが話が早い。