Q&A
チューリングマシンの定義を確認しましょう(^_-)
知りたいこと
僕はプログラミングをしています。
そして最近、プログラミング言語の定義ってなんだろう...
と思って調べたりしていたら、プログラミング言語の(一般的な)定義のしかたは
「チューリング完全」かどうかだそうです...
まずそれが正しいか教えて下さい。
試してみたこと
検索をしました。その中で最も分かりやすいであろう回答はこうでした
**計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。。**でした。
疑問
万能チューリングマシンというのは
電卓みたいなものなのでしょうか...?
でもそうすると...電卓もチューリング完全になってしまいますよね...
わけがわからないのです...
回答8件
0
ベストアンサー
プログラミング言語の(一般的な)定義のしかたは「チューリング完全」かどうかだそうです...
「プログラミング言語はチューリング完全である」は事実ですが、これはプログラミング言語自身の記述能力（＝どのような問題を解けるか？）を表しているだけです。なのでプログラミング言語の“定義のしかた”という言い回しには違和感がのこります。
一方で“チューリング完全でない(自称)プログラミング言語”、例えば HQ9+ はジョーク目的で実用上は使い物になりませんから、完全に誤った主張とも言い切れないです。
万能チューリングマシンというのは電卓みたいなものなのでしょうか...?
でもそうすると...電卓もチューリング完全になってしまいますよね...
あなたの考える“電卓”の定義にもよりますが、四則演算や√や冪乗といった計算ができる程度の“普通の電卓”はチューリング完全 ではありません。
検索をしました。その中で最も分かりやすいであろう回答はこうでした
計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。。でした。
（上記説明でご自身が納得されたならば、それで十分かと思います。“既に理解している人向けの説明”感が強いですが...）
万能チューリングマシンについては 情報処理学会研究報告「万能チューリング機械のわかりやすい動作説明」 などの説明を参照ください。もしくは Brainfuck というプログラミング言語を調べてみるのも良いかと思います。
ある「対象◯◯がチューリング完全である」といった場合、その「対象◯◯を使えば（どんなに非効率的であっても）普通のプログラミング言語と同程度の計算問題を解ける」ことを意味します。ただし、あくまでも“純粋な数値計算”に限りますから、インタラクティブなゲームを作れたりネットワーク通信ができる訳ではありません。
おまけ：記事「うっかりチューリング完全になっちゃったもの」では、その設計者が 意図せず チューリング完全という性質を備えてしまった何かがリストアップされています。興味があればのぞいてみてください。
投稿2019/03/21 14:43
編集2019/03/22 00:29
総合スコア6191
「うっかりチューリング完全になっちゃったもの」読んでみましたが、何がチューリング完全なのかわかりませんでした。複雑なものを挙げているだけのジョークのように見えます。
マジック・ザ・ギャザリングでフィボナッチ数列や円周率を求めたりできるんでしょうか？
> マジック・ザ・ギャザリングでフィボナッチ数列や円周率を求めたりできるんでしょうか？
はい。命題「マジック・ザ・ギャザリングはチューリング完全である」が真であれば、理論上はフィボナッチ数列も円周率も計算できます。（実際の処理過程はおそろしく非効率的なものになるでしょうけども）
この命題が真であるか否かは、私自身では判断できません。そもそもゲームの名前しか知らないです。 http://d.hatena.ne.jp/kkishi/20171104 などを参照されてみてはいかがでしょう。
ほほう。これはすごいですね。
チューリング完全の議論では「定義された手続きの塊」が対象になるので、マジック・ザ・ギャザリングのようなゲームでさえも考慮対象になりえますね。
Zuishinさんが仰る通り「複雑なもの」＝複雑怪奇なルール集合体になっていく過程で、ついうっかり／びっくりなぜかチューリング完全という性質を備えてしまったものがリストアップされています。
もう少しコンピュータ寄りの例だと https://cpplover.blogspot.com/2015/06/x86mov.html x86プロセッサのMOV命令というただ1つのCPU命令が、チューリング完全になってしまっています。言い換えると「MOV命令をただひたすら並べただけであらゆる計算ができてしまう」ということです。もはや意味不明ですが:P https://github.com/xoreaxeaxeax/movfuscator でサンプルを見られます。
ありがとうございます。これもなかなかに興味深い記事です。
0
こんにちは。
プログラミング言語の(一般的な)定義のしかたは
「チューリング完全」かどうかだそうです...
まずそれが正しいか教えて下さい。
プログラミング言語を定義する際に、チューリング完全かどうかを気にする人はあまりいないと思います。
普通に「有用」なプログラミング言語を定義したら、それは大抵のケースでチューリング完全です。
また「有用」なプログラミング言語（の一部）でもチューリング完全でないものもあります。C言語のプリプロセッサは有る種の独立したプログラミング言語であり単独で使うことも可能（そのようなことをするケースはほぼないとは思いますが、皆無でもないだろうと予想しています）ですが、チューリング完全ではありません。
ですので、「チューリング完全」かどうかはプログラミング言語の特性の１つと捉えた方が良いと思います。
万能チューリングマシンというのは
電卓みたいなものなのでしょうか...?
そのような結論を導いた道筋が読めませんが、それは違います。
電卓と同じ振る舞いをするチューリングマシンを定義することは可能と思いますが、電卓は電卓であって他の機能を持てないので「万能」ではありません。
投稿2019/03/21 03:05
総合スコア23274
0
万能チューリングマシンというのは
電卓みたいなものなのでしょうか...?
違います。無限長テープとヘッドを持つ機械です。
Wikipediaを読んで理解できればいいのですが、難しいようであればオートマトンを基礎から勉強していくとそのうちチューリングマシンにたどり着くと思います。
直感的には、
- データ（どれほど膨大であってもいい）がある
- データを処理するルール（どれほど膨大で複雑であってもいいが、ちゃんと形式的に定義できて矛盾しないもの）がある
- ルールに則ってデータを処理する
みたいなことができればチューリング完全です。ただし「メモリに乗り切らない計算はできないのでチューリング完全ではないね」とは言わないお約束になっています（と思います）。
投稿2019/03/21 21:12
編集2019/03/21 21:34
総合スコア30939
“「メモリに乗り切らない計算はできないのでチューリング完全ではないね」とは言わないお約束”
最近のHDDをメモリの延長と考えれば、膨大なデータ＋膨大なルールも少しは実現可能かと。
TB単位のデータとTB単位のルール・・・無限長にはなりませんが・・・しかしTB単位のデータは分かるけど、TB単位の矛盾のないルールって人間の頭で考えられるんだろうか？
認識できるHDDの容量にも限界がありますからねぇ。あと断っておきますが、「そういったことは言語仕様に含まれていないので実装の問題と言える」という議論は不問とします。
＞TB単位のルールって人間の頭で考えられるんだろうか？
できなければ機械的に生成すればいいので、別に難しくはないかと。たとえば「インタプリタ言語の上でその言語で書かれたインタプリタを動作させる」みたいなのを延々と積んでいくだけですね。これなら人間の頭でも考えられます。あるいは単に1+1+1+1+.....（ンTBに達するまで続ける）....+1みたいなのでも良い訳で。
もし、乗算命令が１バイトで書けたら・・・
１×２×３×・・・・を１TB(１兆）ではいくつになるか？ とか考えてしまったｗ・・・メモリのほうがアウトかなぁ
0
「チューリングマシンXを記号化した記号列と、Xに与えるデータの列Dを食わすとXにDを食わせたのとまったく同じ動作をするチューリングマシン」のこと。
チューリングマシンを模倣するチューリングマシンですな。
で、万能チューリングマシンと同じ能力のある計算モデルがチューリング完全です。
どんなプログラムであってもあなたが電卓を使ってそのプログラムを模倣できるなら、
「あなた+電卓」はチューリング完全じゃないかな。
投稿2019/03/20 23:49
編集2019/03/20 23:56
総合スコア16612
>Xに与えるデータの列Dを食わす
が
>XにDを食わせたのとまったく同じ動作をする
っていうのがチューリング完全なんですね...?
では、その記号化したXにデータを与えるってどういう意味なのでしょうか。
また"食わす"ってどういうことですか？
Xが関数、DがXに与える引数だと思っておくれ。
そのときTに X と D を与えると X(D) を実行してくれる(いかなるX,Dの組み合わせに対しても)なら、
Tは万能チューリングマシン。
なるほど...
言葉にしていただいてありがとうございます...
プログラムにするとわかりやすいでしょうか？
なにを?
ごめんなさい、Xが関数でDがXに与える引数ってところで
言葉のまま理解するより抽象化したほうがわかりやすいかなぁと思って
プログラムにすることが抽象化なんですか? プログラムなんて思いっきり具象じゃないかと。実際にモノがあるし動くし。
0
回答ではありません。
以下を確認してみてください。。その上で、質問内容を見直してみましょう。
チューリングマシン
また、チューリング賞は、計算機科学分野で「世界最高の権威」を持つ賞とされています。
興味があったらアラン・チューリングも見てみるといいと思います。
投稿2019/03/21 09:36
総合スコア6851
0
普通の電卓に分岐は無いので電卓を使ったチューリングマシン並みのプログラミングは無理だと思います。
例えば迷路探索を電卓のみで行おうとすれば、どうしても人間の判断が必要になり、自動化できません。
投稿2019/03/21 00:31
総合スコア28673
0
それそのまま「チューリング完全」でぐぐって、でてきたものを一通り読んでみよう。
その上で改めて聞いていただけるとよろしいかと。
投稿2019/03/20 23:48
総合スコア88163
はい、そのうえで、聞いていてその中で最もいんじゃないかな、と思ったのを選んだのです。
それを読んでるなら、それらの記述のわからないところ、疑問に思うことを質門として、その記述を理解しましょう。
まずはそれからのはなしですぜ。
えっと..それは
>疑問
---
万能チューリングマシンというのは
電卓みたいなものなのでしょうか...?
でもそうすると...電卓もチューリング完全になってしまいますよね...
わけがわからないのです...
ここではなくて...?
一通り読んだ上でのその質門なら、もちっと基本的なところから学ぶ必要があるように思います
電卓みたいなものです。電卓もチューリング完全なのです。と言う回答をしたら、あなたはそこからなにかを理解できるのでしょうか
あなたの回答
tips
プレビュー
