- ベストアンサー
チューリングマシンについて
計算理論の勉強をしています。 チューリングマシンが、ある言語を「判定する」というのと「認識する」ということの違いがよくわかりません。 どなたか解説していただけないでしょうか。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
関連するQ&A
- チューリングマシンとオートマトンでできることの違い
チューリングマシンとオートマトンでできることの違いは、具体例で言うとどういうことでしょうか？ 計算理論の本を一生懸命読んでいて、数式が多くてまだ完全に理解できてないのですが、私の理解した範囲で書くと、 ●「チューリングマシン」 ＝ 「オートマトン」 ＋ 「テープ（記憶）」 ですよね。 そして、ネットで調べると、「オートマトン」の例として自動販売機があって、これは非常に理解できました。 「チューリングマシン」の例としてはコンピュータがあって、これはこれで理解できました。 しかし、自動販売機にできなくてコンピュータにできること、の違いがよく分かりません。自動販売機にテープをつけると具体的にどういうメリットがあるのでしょうか？ 他の例でも良いので、チューリングマシンとオートマトンでできることの違いを具体例で教えていただけると幸いです。 ぜひ、よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- チューリングマシンの状態数について
この質問で言うチューリングマシンは、 「使用できる文字が0,1,Xだけのもの」とします。 自然数nに対し、 「空列を入力して動作を開始すると、有限ステップで停止して、停止したときにテープに書き残されている文字数がn以上」 であるようなチューリングマシンを全て集めた集合をKnとします。 そして、 g(n)= min{size(M) | M∈Kn } とします。ただし、size(M)はチューリングマシンMの状態数であり、minは「最小値」を意味します。 各nに対してKnは非空集合なので、g(n)の値はどんなnに対しても一意に定義されます。 すなわち、gは自然数上の全域関数です。 ビジービーバー関数は「状態数」から「その状態数のチューリングマシンが書き残せる最大字数」を求めるものでありますが、 この関数gは「字数」から「それ以上の字数を書き残せるチューリングマシンの最小状態数」を求めるものです。 このgが計算可能であるか、計算不可能であるかを述べて、そのことを証明してください。 よろしくお願いいたします。 ((関数が)計算可能の定義は、「それを計算するＣ言語プログラムが存在する」です。)
- ベストアンサー
- C・C++・C#
- チューリング完全とは何か？
プログラムのチューリング完全性とか万能チューリング機械ってあるじゃないですか。これって、どんな挙動のプログラムでも１言語で書けるって事ですか？ 色々と調べてみたのですが、どのサイトもどの資料も説明が難しかったので、ここで質問してます。私の認識は下の通りです。 チューリング完全のプログラムは、FORTRAN、Ｃ言語、Java、JavaScriptなど。 チューリング不完全のプログラムは、TeX、HTML、SQLなど。 要するに、 TeXは数式や楽譜の作成くらいの機能に制限されている。その一方で、FORTRANは数学的計算は勿論、３Ｇゲームや通販サイトなどFORTRAN１言語だけで何でも出来て、ありとあらゆるシステム構築に使えるって事ですか？ チューリングは、戦前イギリスの数学者の名前。彼は次の命題の証明をした。どんな複雑なコンピューターシステムでも中身を分析すれば、四則演算や条件分岐や反復など数種類の小さな基本的システムパーツの組合せになっている。FORTRANやＣ言語はこれを全て含んでいるから、FORTANは何でも出来る。一方、SQLは惜しいがチューリング完全に必須の基本的システムパーツが数種類だけ欠けていて、限界がある。SQLオンリーでゲームを作ろうとすれば、テトリスくらいなら出来るけど、ぷよぷよを作ろうとすれば別の言語を足す事になる。 正しいですか？
- ベストアンサー
- C・C++・C#
- チューリングマシン テープのn次元拡張について
通常のチューリングマシンは１次元のテープで、ヘッドが右か左に動くのですが、 これを２次元、３次元・・・に拡張した場合のチューリングマシンについての議論を調べています。 （２次元の場合、平面上のセルでヘッドが東西南北に動くようものを想定しています） いずれも、通常のチューリングマシンに還元可能されるとのことですが、 このあたりの議論や解説が載っている本、あるいはＷｅｂページがありましたら教えてください。 ついでに、ヘッドのアルファベット読み取り・書き込みが１個のデータでなくｎ個のデータの場合（テープが一本幅ではなくｎ本幅）にも通常のチューリングマシンに還元可能とのことですが、上記のｎ次元チューリングマシンでも通常のチューリングマシンに還元可能なのでしょうか。 数学は素人同然なので、質問が曖昧であることにはあらかじめ謝罪しておきます。
- ベストアンサー
- 数学・算数
- コンピューターサイエンスのチューリングとは何者なの
コンピューターサイエンスのチューリングとは何者なのでしょうか？ チューリングの計算理論とは何なのか、分かりやすく説明してください。
- ベストアンサー
- 情報工学
- 状態遷移図とチューリングマシンとは
アルゴリズムについて学んでいた際、 「状態遷移図」と「チューリングマシン」という言葉が出てきました。 この二つはどういう関係と意味を持っているのでしょうか？ 調べてみたのですがオートマトンやら難しい計算式ばかり出てきてあまり理解できませんでした。 計算式を見て理解できないならそれまでなのかもしれませんが、 何か比較的簡単な説明を頂けないでしょうか？ お願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- 計算モデルやプログラミング言語について
なぜ何種類もの計算モデル（チューリングマシーン、帰納的関数など）とプログラミング言語（C、FT、Schemeなど）があるのですか？
- ベストアンサー
- その他（プログラミング・開発）
- 万能な記述形態って何種類あるのでしょうか？
プログラマをやっています プログラミング言語を見ていくと ・アセンブラ→C言語→Javaの流れ チューリングマシンから、よく使うものを文法として括り出してきた ・Lisp ラムダ算法をプログラミング言語に落とし込んだ ・Prlog 述語論理をプログラミング言語に落としこんさ という風に、それぞれ元になっているモデルが違いますが それぞれが万能な記述形態で、どんな計算でも出来る記述携帯になっています それで疑問に思ったのですが 他にも万能な記述形態として知られている算法というのは他に何種類あるのでしょうか？ 大学の初等数学までしか知らない人間レベルで分かる解説サイトなどもあれば教えて下さい
- ベストアンサー
- 数学・算数
- タイムマシンの可能性
専門的な科学の知識も無い自分が、ぼんやりと考えたことなのですが… 以下の文章というか理論めいた事は正しいでしょうか？ 「今、自分が生きている時間上の未来では、人類が滅亡するまでタイムマシンは完成しなかった」 もしどこかの未来でタイムマシンが完成していたとしたら、現在か過去のどこかに未来人が現れていて、 「タイムマシンは日常にありえるもの」 になっているはずですが、その事実が無いということは、上記の理論（？）が成り立つのではないかと思ったのです。 この質問に回答して頂ける方にお願いなのですが、計算式などで説明して頂くと、恐らく私には理解できないと思いますので、出来るだけわかりやすい文章でお願いします。 質問する身でいながら我侭なお願い申し訳ありません。 よろしくお願いします。
- ベストアンサー
- 科学
- チューリングマシン
チューリングマシン 現在の状態 0 0 0 0 1 1 1 読んだ文字 0 1 X □ 0 0 1 ーーーーーーーーーーーーーーーー...以下略 次の状態 1 2 0 終 1 3 1 書く文字 □ □ □ □ ０ X X 移動方向 右 右 右 右 左 右 「０」「１」が連続して書かれていて、調べたい０，１の前後は□になっています。 左から一文字ずつ消していき、その際左端が０なら１を、１なら０を1つ消す。 このチューリングマシンは、このようにして「０」「１」の数がちょうど等しいかどうかを調べるものらしいのですが、どうして次の状態に２，３がでてくるのか?また、なぜ左に戻ったりするのか？などいまいちよくわかりません。 詳しく載っているサイトか、説明をお願いします。
- 締切済み
- 数学・算数
