問題タブ [turing-machines]

「辞書」とは、一意のキーを持つキーと値のペアの配列を意味します。そうでない場合、なぜですか？十分な長さであれば、キーを入力として、値を出力として使用でき、必要なだけ多くの問題の解決策を得ることができます。可能なすべての入力を保持するのに十分な長さである限り、何でも「計算」できます。入力に一定量のビットがあることが確立されている限り、これは無限である必要はありません。したがって、入力が X ビットであることに同意した場合、必要なのは 2^X 項目の辞書だけであり、X ビットを入力として受け取る可能性のあるすべてのチューリング マシンが得られます。

右？そうではないと思いますが、なぜですか？

スターバックスのミニ言語メニュー システムをある種の文法またはステート マシンとして解釈するとしたら、その文法はチューリング完全でしょうか? スターバックスの注文ミニ言語の説明は、ここにあります。

I would like to be able to give students an awareness of exactly what happens during program execution inside a modern computer - e.g. use of memory addresses, references, stack, heap and so on.

Ideally I'd like for them to be able to play with some kind of demo where a simple application (e.g. calculator, rudimentary database etc.) runs and can be paused and the state of the machine running the program viewed at quite a low level via a 'pretty' GUI.

Does such an application exist? And if not, could any super-coders advise on the feasibility of writing a piece of software like this? The target audience are probably 1st year Comp Sci students learning a modern OO language (C#, Java ideally).

EDIT:

I thought this had gone cold but someone posted today so I thought I'd better update...

I should probably have put the words 'Turing' and 'machine' into this question. I think people thought I wanted to debug Windows or something when actually I was just thinking of TMs. This is a pretty good simulator, though not pretty by today's standards.

If anyone knows of any others, I'd appreciate you posting a link. Thanks.

次の言語Lは決定不能ですか？

L = { M | Mはチューリングマシンの記述であり、 Mが最大kステップ後に停止するような長さkの入力xが存在します}

そうだと思いますが、証明できませんでした。停止性問題からの削減を考えてみました。

非決定性アルゴリズムの簡単な説明が必要です。非決定性アルゴリズムを並列プロセッサを搭載したコンピュータと比較できますか? 非決定性アルゴリズムについて誰か正確に説明してください

誰かがbrainfuckインタプリタのためのセルオートマトンルールのセットを持っていますか？万能チューリング機械の実装に似ていると思います。それらはwolframサイトに存在しますが、BFシステム用にそれらを微調整する方法がわかりません。

コンピュータアルゴリズムの設計と分析の私のコピーが本日届きました。最初の章では、著者はチューリングマシンを紹介しました。他に2つのアルゴリズムの教科書、アルゴリズム入門とアルゴリズム設計マニュアルがありますが、アルゴリズムとデータ構造の分野で有名ですが、チューリングマシンについてはどれも説明していません。

チューリングマシンとアルゴリズム/データ構造の関係を理解し​​たい。チューリングマシンを理解してアルゴリズムの専門家になることは本当に重要ですか？

チューリングマシンの時間計算量と空間計算量の定義は同じであり、それらを区別することはできないと思います。

私を助けてください。ありがとう。

与えられた n 状態のビジー ビーバー ゲームについて、ビジー ビーバー関数は一意ですか、それとも最大スコアが同じ複数の関数が存在する可能性がありますか? おそらく、どちらの方法でも証明されていませんか？

チューリングマシンでは、（異なる）テープが入力と出力の両方に使用され、スタックにも使用されることを知っています。チューリング マシンを使用して 2 つの数値を加算する問題では、入力は 1、0、B(空白)、+ などの多くの記号を処理しています。

（この質問は物理学に関連していますが、チューリングマシンとその入力について知らないかもしれないと思ったので、ここで質問しました。）

入力が BBBBB1111+111111BB の場合、磁気テープでは、

1->北極で表されます（たとえば）。
0->南極で表されます（たとえば）。
B->極性なしで表されます。

では、「+」はどのように表現されるのでしょうか。特殊記号用のコード (ASCII など) があるとは思いません。特殊シンボルの数とタイプは実装に依存するためです。また、特別なコードはアルゴリズムをより退屈なものにします。

また

テープでの入力記号の表現は、上記の方法とはまったく違うのでしょうか? はいの場合、説明してください。