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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

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

Java

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

JavaScript

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

Python

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

Q&A

解決済

8回答

10340閲覧

チューリング完全とは

TOOO

総合スコア40

C

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

Java

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

JavaScript

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

Python

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

3グッド

3クリップ

投稿2019/03/20 23:40

知りたいこと

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

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

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

DrqYuto, yohhoy, hood👍を押しています

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

cateye

2019/03/21 00:43

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

2019/03/23 08:24

はい!
guest

回答8

0

ベストアンサー

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

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

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

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

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


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

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

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

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

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

投稿2019/03/21 14:43

編集2019/03/22 00:29
yohhoy

総合スコア6189

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2019/03/21 15:00

「うっかりチューリング完全になっちゃったもの」読んでみましたが、何がチューリング完全なのかわかりませんでした。複雑なものを挙げているだけのジョークのように見えます。 マジック・ザ・ギャザリングでフィボナッチ数列や円周率を求めたりできるんでしょうか?
yohhoy

2019/03/21 15:07 編集

> マジック・ザ・ギャザリングでフィボナッチ数列や円周率を求めたりできるんでしょうか? はい。命題「マジック・ザ・ギャザリングはチューリング完全である」が真であれば、理論上はフィボナッチ数列も円周率も計算できます。(実際の処理過程はおそろしく非効率的なものになるでしょうけども) この命題が真であるか否かは、私自身では判断できません。そもそもゲームの名前しか知らないです。 http://d.hatena.ne.jp/kkishi/20171104 などを参照されてみてはいかがでしょう。
Zuishin

2019/03/21 15:07

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

2019/03/21 15:16

チューリング完全の議論では「定義された手続きの塊」が対象になるので、マジック・ザ・ギャザリングのようなゲームでさえも考慮対象になりえますね。 Zuishinさんが仰る通り「複雑なもの」=複雑怪奇なルール集合体になっていく過程で、ついうっかり/びっくりなぜかチューリング完全という性質を備えてしまったものがリストアップされています。 もう少しコンピュータ寄りの例だと https://cpplover.blogspot.com/2015/06/x86mov.html x86プロセッサのMOV命令というただ1つのCPU命令が、チューリング完全になってしまっています。言い換えると「MOV命令をただひたすら並べただけであらゆる計算ができてしまう」ということです。もはや意味不明ですが:P https://github.com/xoreaxeaxeax/movfuscator でサンプルを見られます。
Zuishin

2019/03/21 15:25

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

0

こんにちは。

プログラミング言語の(一般的な)定義のしかたは

「チューリング完全」かどうかだそうです...
まずそれが正しいか教えて下さい。

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

万能チューリングマシンというのは

電卓みたいなものなのでしょうか...?

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

投稿2019/03/21 03:05

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

万能チューリングマシンというのは

電卓みたいなものなのでしょうか...?

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

チューリングマシン - Wikipedia

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

直感的には、

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

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

投稿2019/03/21 21:12

編集2019/03/21 21:34
hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

cateye

2019/03/21 21:32 編集

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

2019/03/21 21:36 編集

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

2019/03/22 10:10

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

0

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

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

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

投稿2019/03/20 23:49

編集2019/03/20 23:56
episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

TOOO

2019/03/20 23:59

>Xに与えるデータの列Dを食わす が >XにDを食わせたのとまったく同じ動作をする っていうのがチューリング完全なんですね...? では、その記号化したXにデータを与えるってどういう意味なのでしょうか。 また"食わす"ってどういうことですか?
episteme

2019/03/21 00:04

Xが関数、DがXに与える引数だと思っておくれ。 そのときTに X と D を与えると X(D) を実行してくれる(いかなるX,Dの組み合わせに対しても)なら、 Tは万能チューリングマシン。
TOOO

2019/03/21 00:09

なるほど... 言葉にしていただいてありがとうございます... プログラムにするとわかりやすいでしょうか?
TOOO

2019/03/21 00:25 編集

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

2019/03/21 00:27

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

0

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

投稿2019/03/21 09:36

cateye

総合スコア6851

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

プログラミング言語

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

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

投稿2019/03/21 03:16

jimbe

総合スコア12543

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

投稿2019/03/21 00:31

Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

投稿2019/03/20 23:48

y_waiwai

総合スコア87719

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

TOOO

2019/03/20 23:53

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

2019/03/20 23:58

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

2019/03/21 00:01

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

2019/03/21 09:45

一通り読んだ上でのその質門なら、もちっと基本的なところから学ぶ必要があるように思います 電卓みたいなものです。電卓もチューリング完全なのです。と言う回答をしたら、あなたはそこからなにかを理解できるのでしょうか
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問