質問: 知りたいこと ------ 僕はプログラミングをしています。 そして最近、プログラミング言語の定義ってなんだろう... と思って調べたりしていたら、プログラミング言語の(一般的な)定義のしかたは 「チューリング完全」かどうかだそうです... まずそれが正しいか教えて下さい。 試してみたこと ------- 検索をしました。その中で最も分かりやすいであろう回答はこうでした **計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全(チューリングかんぜん、Turing-complete)あるいは計算完備であるという。。**でした。 疑問 -- 万能チューリングマシンというのは 電卓みたいなものなのでしょうか...? でもそうすると...**電卓もチューリング完全**になってしまいますよね... わけがわからないのです...
回答: > > プログラミング言語の(一般的な)定義のしかたは「チューリング完全」かどうかだそうです... > > > 「プログラミング言語はチューリング完全である」は事実ですが、これはプログラミング言語自身の記述能力(=どのような問題を解けるか?)を表しているだけです。なのでプログラミング言語の“定義のしかた”という言い回しには違和感がのこります。 一方で“チューリング完全でない(自称)プログラミング言語”、例えば HQ9+ はジョーク目的で実用上は使い物になりませんから、完全に誤った主張とも言い切れないです。 > > 万能チューリングマシンというのは電卓みたいなものなのでしょうか...? > > でもそうすると...電卓もチューリング完全になってしまいますよね... > > > あなたの考える“電卓”の定義にもよりますが、四則演算や√や冪乗といった計算ができる程度の“普通の電卓”はチューリング完全 **ではありません**。 > > 検索をしました。その中で最も分かりやすいであろう回答はこうでした > > 計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全(チューリングかんぜん、Turing-complete)あるいは計算完備であるという。。でした。 > > > (上記説明でご自身が納得されたならば、それで十分かと思います。“既に理解している人向けの説明”感が強いですが...) 万能チューリングマシンについては 情報処理学会研究報告「万能チューリング機械のわかりやすい動作説明」 などの説明を参照ください。もしくは Brainfuck というプログラミング言語を調べてみるのも良いかと思います。 ある「対象◯◯がチューリング完全である」といった場合、その「対象◯◯を使えば(どんなに非効率的であっても)普通のプログラミング言語と同程度の計算問題を解ける」ことを意味します。ただし、あくまでも“純粋な数値計算”に限りますから、インタラクティブなゲームを作れたりネットワーク通信ができる訳ではありません。 おまけ:記事「うっかりチューリング完全になっちゃったもの」では、その設計者が **意図せず** チューリング完全という性質を備えてしまった何かがリストアップされています。興味があればのぞいてみてください。