質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.35%

  • JavaScript

    22095questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

  • Java

    16752questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

  • Python

    13377questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • C

    4946questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

チューリング完全とは

解決済

回答 8

投稿

  • 評価
  • クリップ 3
  • VIEW 1,335

TOOO

score 34

知りたいこと

僕はプログラミングをしています。
そして最近、プログラミング言語の定義ってなんだろう...
と思って調べたりしていたら、プログラミング言語の(一般的な)定義のしかたは
「チューリング完全」かどうかだそうです...
まずそれが正しいか教えて下さい。

試してみたこと

検索をしました。その中で最も分かりやすいであろう回答はこうでした
計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全(チューリングかんぜん、Turing-complete)あるいは計算完備であるという。。でした。

疑問

万能チューリングマシンというのは
電卓みたいなものなのでしょうか...?
でもそうすると...電卓もチューリング完全になってしまいますよね...
わけがわからないのです...

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • cateye

    2019/03/21 09:43

    チューリングマシンの定義を確認しましょう(^_-)

    キャンセル

  • TOOO

    2019/03/23 17:24

    はい!

    キャンセル

回答 8

checkベストアンサー

+4

プログラミング言語の(一般的な)定義のしかたは「チューリング完全」かどうかだそうです...

「プログラミング言語はチューリング完全である」は事実ですが、これはプログラミング言語自身の記述能力(=どのような問題を解けるか?)を表しているだけです。なのでプログラミング言語の“定義のしかた”という言い回しには違和感がのこります。

一方で“チューリング完全でない(自称)プログラミング言語”、例えば HQ9+ はジョーク目的で実用上は使い物になりませんから、完全に誤った主張とも言い切れないです。

万能チューリングマシンというのは電卓みたいなものなのでしょうか...?
でもそうすると...電卓もチューリング完全になってしまいますよね...

あなたの考える“電卓”の定義にもよりますが、四則演算や√や冪乗といった計算ができる程度の“普通の電卓”はチューリング完全 ではありません


検索をしました。その中で最も分かりやすいであろう回答はこうでした
計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全(チューリングかんぜん、Turing-complete)あるいは計算完備であるという。。でした。

(上記説明でご自身が納得されたならば、それで十分かと思います。“既に理解している人向けの説明”感が強いですが...)

万能チューリングマシンについては 情報処理学会研究報告「万能チューリング機械のわかりやすい動作説明」 などの説明を参照ください。もしくは Brainfuck というプログラミング言語を調べてみるのも良いかと思います。

ある「対象◯◯がチューリング完全である」といった場合、その「対象◯◯を使えば(どんなに非効率的であっても)普通のプログラミング言語と同程度の計算問題を解ける」ことを意味します。ただし、あくまでも“純粋な数値計算”に限りますから、インタラクティブなゲームを作れたりネットワーク通信ができる訳ではありません。

おまけ:記事「うっかりチューリング完全になっちゃったもの」では、その設計者が 意図せず チューリング完全という性質を備えてしまった何かがリストアップされています。興味があればのぞいてみてください。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/22 00:07

    ほほう。これはすごいですね。

    キャンセル

  • 2019/03/22 00:16

    チューリング完全の議論では「定義された手続きの塊」が対象になるので、マジック・ザ・ギャザリングのようなゲームでさえも考慮対象になりえますね。

    Zuishinさんが仰る通り「複雑なもの」=複雑怪奇なルール集合体になっていく過程で、ついうっかり/びっくりなぜかチューリング完全という性質を備えてしまったものがリストアップされています。

    もう少しコンピュータ寄りの例だと https://cpplover.blogspot.com/2015/06/x86mov.html x86プロセッサのMOV命令というただ1つのCPU命令が、チューリング完全になってしまっています。言い換えると「MOV命令をただひたすら並べただけであらゆる計算ができてしまう」ということです。もはや意味不明ですが:P https://github.com/xoreaxeaxeax/movfuscator でサンプルを見られます。

    キャンセル

  • 2019/03/22 00:25

    ありがとうございます。これもなかなかに興味深い記事です。

    キャンセル

+2

こんにちは。

プログラミング言語の(一般的な)定義のしかたは
「チューリング完全」かどうかだそうです...
まずそれが正しいか教えて下さい。

プログラミング言語を定義する際に、チューリング完全かどうかを気にする人はあまりいないと思います。
普通に「有用」なプログラミング言語を定義したら、それは大抵のケースでチューリング完全です。
また「有用」なプログラミング言語(の一部)でもチューリング完全でないものもあります。C言語のプリプロセッサは有る種の独立したプログラミング言語であり単独で使うことも可能(そのようなことをするケースはほぼないとは思いますが、皆無でもないだろうと予想しています)ですが、チューリング完全ではありません。
ですので、「チューリング完全」かどうかはプログラミング言語の特性の1つと捉えた方が良いと思います。

万能チューリングマシンというのは
電卓みたいなものなのでしょうか...?

そのような結論を導いた道筋が読めませんが、それは違います。
電卓と同じ振る舞いをするチューリングマシンを定義することは可能と思いますが、電卓は電卓であって他の機能を持てないので「万能」ではありません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

万能チューリングマシンというのは
電卓みたいなものなのでしょうか...?

違います。無限長テープとヘッドを持つ機械です。

チューリングマシン - Wikipedia

Wikipediaを読んで理解できればいいのですが、難しいようであればオートマトンを基礎から勉強していくとそのうちチューリングマシンにたどり着くと思います。

直感的には、

  • データ(どれほど膨大であってもいい)がある
  • データを処理するルール(どれほど膨大で複雑であってもいいが、ちゃんと形式的に定義できて矛盾しないもの)がある
  • ルールに則ってデータを処理する

みたいなことができればチューリング完全です。ただし「メモリに乗り切らない計算はできないのでチューリング完全ではないね」とは言わないお約束になっています(と思います)。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/22 06:23 編集

    “「メモリに乗り切らない計算はできないのでチューリング完全ではないね」とは言わないお約束”
    最近のHDDをメモリの延長と考えれば、膨大なデータ+膨大なルールも少しは実現可能かと。
    TB単位のデータとTB単位のルール・・・無限長にはなりませんが・・・しかしTB単位のデータは分かるけど、TB単位の矛盾のないルールって人間の頭で考えられるんだろうか?

    キャンセル

  • 2019/03/22 06:31 編集

    認識できるHDDの容量にも限界がありますからねぇ。あと断っておきますが、「そういったことは言語仕様に含まれていないので実装の問題と言える」という議論は不問とします。
    >TB単位のルールって人間の頭で考えられるんだろうか?
    できなければ機械的に生成すればいいので、別に難しくはないかと。たとえば「インタプリタ言語の上でその言語で書かれたインタプリタを動作させる」みたいなのを延々と積んでいくだけですね。これなら人間の頭でも考えられます。あるいは単に1+1+1+1+.....(ンTBに達するまで続ける)....+1みたいなのでも良い訳で。

    キャンセル

  • 2019/03/22 19:10

    もし、乗算命令が1バイトで書けたら・・・
    1×2×3×・・・・を1TB(1兆)ではいくつになるか? とか考えてしまったw・・・メモリのほうがアウトかなぁ

    キャンセル

0

それそのまま「チューリング完全」でぐぐって、でてきたものを一通り読んでみよう。
その上で改めて聞いていただけるとよろしいかと。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/21 08:53

    はい、そのうえで、聞いていてその中で最もいんじゃないかな、と思ったのを選んだのです。

    キャンセル

  • 2019/03/21 08:58

    それを読んでるなら、それらの記述のわからないところ、疑問に思うことを質門として、その記述を理解しましょう。
    まずはそれからのはなしですぜ。

    キャンセル

  • 2019/03/21 09:01

    えっと..それは
    >疑問
     ---
     万能チューリングマシンというのは
     電卓みたいなものなのでしょうか...?
     でもそうすると...電卓もチューリング完全になってしまいますよね...
     わけがわからないのです...
    ここではなくて...?

    キャンセル

  • 2019/03/21 18:45

    一通り読んだ上でのその質門なら、もちっと基本的なところから学ぶ必要があるように思います

    電卓みたいなものです。電卓もチューリング完全なのです。と言う回答をしたら、あなたはそこからなにかを理解できるのでしょうか

    キャンセル

0

「チューリングマシンXを記号化した記号列と、Xに与えるデータの列Dを食わすとXにDを食わせたのとまったく同じ動作をするチューリングマシン」のこと。

チューリングマシンを模倣するチューリングマシンですな。

で、万能チューリングマシンと同じ能力のある計算モデルがチューリング完全です。
どんなプログラムであってもあなたが電卓を使ってそのプログラムを模倣できるなら、
「あなた+電卓」はチューリング完全じゃないかな。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/21 09:12

    なにを?

    キャンセル

  • 2019/03/21 09:24 編集

    ごめんなさい、Xが関数でDがXに与える引数ってところで
    言葉のまま理解するより抽象化したほうがわかりやすいかなぁと思って

    キャンセル

  • 2019/03/21 09:27

    プログラムにすることが抽象化なんですか? プログラムなんて思いっきり具象じゃないかと。実際にモノがあるし動くし。

    キャンセル

0

普通の電卓に分岐は無いので電卓を使ったチューリングマシン並みのプログラミングは無理だと思います。
例えば迷路探索を電卓のみで行おうとすれば、どうしても人間の判断が必要になり、自動化できません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

プログラミング言語

プログラミング言語(プログラミングげんご、英: programming language)とは、コンピュータプログラムを記述するための形式言語である。

こちらで良いような気が致します.

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

回答ではありません。
以下を確認してみてください。。その上で、質問内容を見直してみましょう。
チューリングマシン
また、チューリング賞は、計算機科学分野で「世界最高の権威」を持つ賞とされています。
興味があったらアラン・チューリングも見てみるといいと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.35%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • JavaScript

    22095questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

  • Java

    16752questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

  • Python

    13377questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • C

    4946questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。