目次
を作成し、終了するかどうかを尋ねるプログラムを作成するだけです。 。ただし、停止の決定不可能性は厳密に表現され、証明されなければなりません。 " > を作成し、終了するかどうかを尋ねるプログラムを作成するだけです。 。ただし、停止の決定不可能性は厳密に表現され、証明されなければなりません。
ホームページ テクノロジー周辺機器 AI チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

Apr 16, 2023 pm 02:34 PM
計算する チューリング

1950年10月、「機械は考えることができるか」というタイトルの論文が発表されました。この論文は、通信装置を介して被験者にランダムに質問をし、被験者が被験者の意図を推測するよう求めることで、被験者と被験者(生身の人間と機械)を切り離すという恐ろしいテストを提案しています。話していたのは生身の人間か機械でした。

複数のテストの後、マシンが各参加者に平均 30% 以上の誤った判断をさせることができれば、マシンはテストに合格し、人間の能力を備えていると見なされます。

これは、ロボットが人間の知性を持っている可能性があることに人々が初めて気づいたときです。このテストは、何百万もの SF 愛好家の間で話題になっているチューリング テストです。この論文により、著者アラン・チューリングは「人工知能の父」の称号を獲得しました。

人工知能への道、またはコンピュータ開発の歴史の起源は、チューリングが 24 歳のときに発表した論文です。この論文の中で、彼は「計算可能性」に厳密な数学的定義を与え、有名な「チューリングマシン」のアイデアを提案しました。チューリング マシンは特定のマシンではなく、想像できるすべての計算可能な関数を計算するために使用できる、非常にシンプルだが非常に強力なコンピューティング デバイスを作成できるメンタル モデルです。

チューリングはチューリング マシンを発明したため、時々、チューリングが実際に「コンピューターを発明した」と主張する人がいます。ただし、チューリング マシンは実際のコンピューティング マシンと同じように設計されているわけではありません。チューリング マシンはマシンの抽象モデルですらない。 (チューリングの発言によって証明されるように)チューリングマシンはテーブル上の紙に書いている人をモデルにしたものであることが判明しました。では、チューリングはなぜチューリング マシンを発明したのでしょうか、そしてチューリング マシンは私たちをどこへ導くのでしょうか?

1 チューリングの論文「計算可能な数について」

これらの質問に答える最良の方法は、教科書を脇に置いて、紙を開くことです。現在、1936 年の定期刊行物を借りるには、ローン カードに記入する必要も、図書館員が図書館から本を取りに来るまで 1 時間待つ必要もありません。必要なのはモルト ウイスキーのグラスを手に持ち、自宅で Google に簡単にアクセスできることだけです。私たちが探しているチューリング論文は次のとおりです:

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

論文アドレス: https://www.cs.virginia.edu/ ~robins/Turing_Paper_1936.pdf

論文にはいくつかの誤りがありますが、欠点が欠点を上回るほどではありません。 Joel David Hamkins が述べたように、チューリングは計算可能な実数を、計算可能な 10 進展開を伴う数値として定義しました。これは実際には機能しませんが、修正するのは難しくありません。

チューリングは、「決定問題における計算可能な数とその応用について」というタイトルでこの論文を書いた意図を説明しました。その中の「Entscheidungsproblem (決定問題)」は問いかけます。与えられた 1 次論理式が有効である、つまりすべての解釈で真であると判断するための効率的な手法があるかどうか。

チューリングは、次のようにアイデアを発展させました:

実数を計算している人を、限られた数の条件しか満たせないマシンにたとえることができます。q1、q2、... qR.... このマシンには 1 つだけあります。その中を「紙テープ」が通過し、紙テープはいくつかの部分に分割されます。これらの部分を正方形と呼び、それぞれの正方形には「記号」を入れることができます...書き留める人もいます記号は実数の10進数の列を形成します他の記号は「記憶を助ける」ためのラフなメモです。このラフなメモは消すことができます。私の主張は、このテープ上の滑りです。特定の記号を前後にスワイプして記号を処理するという操作方法です」

……

## 「計算可能な数値」とは、単に 10 進表現が計算できる実数を意味します。私の定義によれば、数値の 10 進表現を機械で書き記すことができれば、その数値は計算可能です。

チューリングはその後、それを定義し、証明しました。これは典型的な数学の論文であり、典型的な工学論文ではありません。この種の記事では、読者はその記事で説明されている特定のメカニズムを実装する方法についての議論を見たいと考えています。チューリングのタイトルと記事から、チューリングの主な関心事であることがわかります。小数点以下無限桁までの実数の計算。

この論文には他にも多くの重要な貢献があります:

  • ユニバーサル チューリング マシン、およびデジタル形式でのエンコード マシンのアイデア
  • この方法でコード化されたマシンの停止問題と対角化の決定不可能性

この論文を書いた後、チューリングは理論的な計算科学を開拓しました。畑への門。

2 ユニバーサル チューリング マシン

チューリングがユニバーサル チューリング マシン (UTM) のアイデアを思いついた理由はわかりませんが、かつて考えてみれば、彼は普遍的なチューリングマシンの存在が明らかだと思っているかもしれません。チューリング マシンの目的は、机で働く事務員をシミュレートすることであり、チューリング マシンの操作は事務員の操作と同じであり、マシンに基づいて指定された変換規則のリストに従って特定の操作を実行します。状態とテープのシンボル - このような日常的なタスクを実行するにはチューリング マシンが明らかに必要です。チューリングの論文は構造の詳細について少し大雑把だったが、誰も気にしていないようだった。

鋭く鮮やかにデザインされた万能チューリングマシンが誕生しました。数十年前、ケンブリッジ大学でケン ムーディ博士が普遍的なミンスキー キー生成を作成しました:

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

リンク: http://www .igblan.free-online.co.uk/igblan/ca/minsky.html

このようなマシンのレジスターは限られており、各レジ​​スターには任意の大きな非負整数を格納できます。これには、3 つの異なるタイプのラベル命令で構成される有限プログラムがあります。

  • レジスタ R をインクリメントし、ラベルにジャンプします。 #L、または #R#L## レジスタ #R
  • をテスト/デクリメントし、ラベル L0/L## にジャンプします #1、または L0↞R−→L1# #割り込み。
  • このようなマシンは、実際のコンピュータのようには見えませんが、チューリング マシンよりもプログラミングが簡単です。
  • Moody は、
N

N×N の間の標準的な全単射を使用して、整数のリストを 1 つの整数にパックします。彼は、スタックのプッシュアップやポップオフなどの操作を実行する小さなレジスタ マシンの小さなライブラリを作成し、実際のプロセッサのフェッチと実行のサイクルを彷彿とさせる設計を作成しました。プロセス全体は次のスライドでご覧いただけます。下の写真はマシン自体です。

下の写真はマシンの全体構造です。 (これら 2 つの写真の作者は、ケンブリッジ大学の理論計算科学教授である Andrew Pitts です。)

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

驚くべきことに、この構造は機械はとてもシンプルです!

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?3

停止問題

停止問題は明らかに決定不可能です。そうしないと、フェルマーの最終定理など、多くの数学的予想を解くのが難しくなります。x、y、z、n>2 を検索し、

を作成し、終了するかどうかを尋ねるプログラムを作成するだけです。 。ただし、停止の決定不可能性は厳密に表現され、証明されなければなりません。

一般的な考えに反して、チューリングの論文では停止問題については議論されていませんでしたが、彼が「循環性」と呼んだ、停止問題に関連する特性について議論しました。チューリング マシンが「限られた数の最初のシンボル (つまり 0 と 1) のみを書き込む」場合、チューリング マシンは循環的です。周期性が重要な理由は、チューリングが実数を無限のバイナリ文字列として近似することを特に好んでいたからだと思います。物理学者のクリストファー・ストレイチーは、1965 年のコンピューター・ジャーナルへの手紙の中で、チューリングが停止問題の決定不可能性の証拠を教えてくれたと主張した。 チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

4 チューリングとモーリス・ウィルクス

2009年9月、デヴィッド・P・アンダーソンはモーリス・ウィルクスにインタビューしましたが、彼のチューリングに対する見方は世間とはまったく逆でした:

David P. Anderson: 決定問題に関するチューリングの 1936 年の論文の重要性は何だと思いますか?

Maurice Wilkes: エンジニアはストアド プログラムのアイデアを一種の聖なる三位一体として見て、こう言うと思います。それがどのように行われるべきかです。」

その論文のアイデアと私が述べたことの間に実質的な違いはありません。彼がその論文を出版できたのは幸運でした。つまり、アロンゾ・チャーチは他の方法を使って同じ結果を得ました。

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

記事アドレス: https://cacm.acm.org/magazine/2009/9/38898-an-interview-with -maurice-wilkes/fulltext

##なお、モーリス ウィルクス氏はインタビュー時点で 96 歳であり、彼自身もコンピュータのパイオニアとして有名な EDSAC (Electronic電子遅延ストレージ自動計算機 Delay Storage Auto Calculator の生みの親。彼の奇妙な答えには、チューリングの高貴な地位に対する彼の嫉妬が見て取れます。この二人は明らかに気が合わない!モーリス・ウィルクスの理論軽視も見られます。プログラムを組み込んだコンピューターでは機械を数値にエンコードすることが期待されていましたが、チューリングの研究は純粋な数学であり、工学的な意味はありませんでした。チューリングは実際のコンピュータ工学に興味を持っていましたが、実際のプロジェクトに参加しようとする試みは何度も挫折しました。

そして、教会に関するこれらの発言をどのように評価しますか?

5 チューリングとプリンストンの教会

チューリングが研究を行っている間、多くの研究者が「効率的な計算可能性」という考えに注目しました。ここで私は読者に Qiu Qi 著『初級整数論の解けない問題』を読むことをお勧めします (下の図を参照)。

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

ペーパーリンク: https://www.jstor.org/stable/2371045?origin=crossref

正直に言うと、この論文は読みにくいですが、私たちを現場に連れて行ってくれます。この記事では、λ 計算の定義、再帰関数 (クリーネ/ゲーデルの意味で) の定義、および λ 計算におけるパラダイムの存在と同等性に関するいくつかの議論の余地のない質問を示します。チャーチとクレイニーはラムダ定義可能な関数と再帰関数が等価であることを証明し、チューリングがプリンストンにいた間にラムダ定義可能な関数とチューリングで計算できる関数の間の等価性も証明されていたので、チャーチとチューリングのテーゼが得られます。これは、効果的に計算可能な関数がまさに数学的同値類の関数であるという事実を指します。

6 教会とチューリングの説は正しいでしょうか?

よく言われることですが、「効率的に計算可能」というのは正確な概念ではないため、この命題が正しいかどうかを証明することはできません。チューリングの計算可能な関数は、宇宙の存続期間内には計算できない関数が多数含まれているため、かなり包括的なクラスとして考えることができます。 Ackermann 関数の助けを借りて、例を簡単に取得できます。

アッカーマン関数の現代形式は次のとおりです:

チューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?

記事リンク: https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html

f(n)=A(n,n) と定義すると、偶数 f(4) の計算は期待できません。 g(n)=A(4,n) は、原始的な再帰ではありますが、計算するのはほとんど不可能です。

1930 年代までデジタル コンピューターはありませんでしたが、効率的な計算能力の概念は数学者にはよく知られていました。妥当性の概念はギリシャ幾何学の直線構造とコンパス構造に古くから登場しており、決定問題やヒルベルトの第 10 問題にも不可欠な部分です。ゲーデルの再帰関数やチャーチのラムダ計算と比較したときのチューリングの概念の優れた点は、それが明らかに正しいということです。ゲーデル自身も、彼の再帰関数が計算の概念を捉えているかどうかはわかりませんでしたし、チャーチの考えが正しかったかどうかもわかりません。チューリングのアイデアだけがシンプルで自然でした。チューリングのアイデアは他のモデルと同等であることが証明されており、それらすべてに合理的な説明を提供します。彼は 1937 年の論文「計算可能性とラムダ定義可能性」でこの事実を指摘しました。

この記事は、著者が提案した 計算可能関数 が Qiu Qi の λ 定義可能関数 および提案された関数 と一致することを証明することを目的としています。 Elbrown と Brother による Del によって提案され、Kleiny によって開発された 一般再帰関数 は同じです。これらの同じ関数は、X で定義されたすべての関数が計算可能であり、すべての計算可能な関数が一般に再帰的であることを証明します。

チューリングは「計算可能」と書きましたが、「チューリング計算可能」と書かなければならないことに注意してください。

###

以上がチューリングマシン: コンピューターが存在しない状況で、どうやってコンピューティングについて語ることができるでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Word文書で足し算、引き算、掛け算、割り算を計算する方法 Word文書で足し算、引き算、掛け算、割り算を計算する方法 Mar 19, 2024 pm 08:13 PM

WORD は強力なワード プロセッサです。Word を使用してさまざまなテキストを編集できます。Excel の表では、足し算、引き算、乗算の計算方法をマスターしました。そのため、Word の表で数値の足し算を計算する必要がある場合は、乗数を引くにはどうすればよいですか? 計算には電卓しか使用できませんか?答えはもちろん「いいえ」です。WORD でも実行できます。今日は、Word文書の表で加算、減算、乗算、除算などの基本的な演算を数式を使って計算する方法を説明しますので、一緒に学びましょう。そこで、今日は、WORD 文書で加算、減算、乗算、除算を計算する方法を詳しく説明します。ステップ 1: WORD を開き、ツールバーの [挿入] の下にある [表] をクリックし、ドロップダウン メニューに表を挿入します。

CUDA の汎用行列乗算: 入門から習熟まで! CUDA の汎用行列乗算: 入門から習熟まで! Mar 25, 2024 pm 12:30 PM

General Matrix Multiplication (GEMM) は、多くのアプリケーションやアルゴリズムの重要な部分であり、コンピューター ハードウェアのパフォーマンスを評価するための重要な指標の 1 つでもあります。 GEMM の実装に関する徹底的な調査と最適化は、ハイ パフォーマンス コンピューティングとソフトウェア システムとハードウェア システムの関係をより深く理解するのに役立ちます。コンピューター サイエンスでは、GEMM を効果的に最適化すると、計算速度が向上し、リソースが節約されます。これは、コンピューター システムの全体的なパフォーマンスを向上させるために非常に重要です。 GEMM の動作原理と最適化方法を深く理解することは、最新のコンピューティング ハードウェアの可能性をより有効に活用し、さまざまな複雑なコンピューティング タスクに対してより効率的なソリューションを提供するのに役立ちます。 GEMMのパフォーマンスを最適化することで

Python の count() 関数を使用してリスト内の要素の数を数える方法 Python の count() 関数を使用してリスト内の要素の数を数える方法 Nov 18, 2023 pm 02:53 PM

Python の count() 関数を使用してリスト内の要素の数を計算する方法には、特定のコード サンプルが必要です。Python は強力で習得しやすいプログラミング言語として、さまざまなデータ構造を処理するための組み込み関数を多数提供しています。その 1 つは count() 関数で、リスト内の要素の数をカウントするために使用できます。この記事では、count()関数の使い方と具体的なコード例を詳しく説明します。 count() 関数は Python の組み込み関数であり、特定の値を計算するために使用されます。

Java で部分文字列の出現数を再帰的にカウントする Java で部分文字列の出現数を再帰的にカウントする Sep 17, 2023 pm 07:49 PM

2 つの文字列 str_1 と str_2 を指定します。目的は、再帰的プロシージャを使用して、文字列 str1 内の部分文字列 str2 の出現数をカウントすることです。再帰関数は、その定義内で自分自身を呼び出す関数です。 str1 が「Iknowthatyouknowthatiknow」、str2 が「know」の場合、出現回数は -3 になります。例を通して理解しましょう。たとえば、入力 str1="TPisTPareTPamTP"、str2="TP"; 出力 Countofoccurrencesofasubstringrecursi

C# で Math.Pow 関数を使用して指定した数値のべき乗を計算する方法 C# で Math.Pow 関数を使用して指定した数値のべき乗を計算する方法 Nov 18, 2023 am 11:32 AM

C# には、多くの数学関数が含まれる Math クラス ライブラリがあります。これらには、累乗を計算する関数 Math.Pow が含まれており、指定された数値の累乗を計算するのに役立ちます。 Math.Pow 関数の使用法は非常に簡単で、基数と指数を指定するだけです。構文は次のとおりです: Math.Pow(base,exponent); ここで、base は基数を表し、exponent は指数を表します。この関数は double 型の結果、つまりべき乗の計算結果を返します。しましょう

行列式を使用して三角形の面積を計算するJavaプログラム 行列式を使用して三角形の面積を計算するJavaプログラム Aug 31, 2023 am 10:17 AM

はじめに 行列式を使用して三角形の面積を計算する Java プログラムは、3 つの頂点の座標を指定して三角形の面積を計算できる簡潔で効率的なプログラムです。このプログラムは、Java で基本的な算術および代数計算を使用する方法と、Scanner クラスを使用してユーザー入力を読み取る方法を示しているため、ジオメトリを学習または操作する人にとって役立ちます。プログラムはユーザーに三角形の 3 点の座標を入力するように要求し、その座標が読み取られて、座標行列の行列式を計算するために使用されます。行列式の絶対値を使用して面積が常に正であることを確認し、式を使用して三角形の面積を計算し、ユーザーに表示します。このプログラムは簡単に変更して、さまざまな形式での入力を受け入れたり、追加の計算を実行したりできるため、幾何学的計算のための多用途ツールになります。決定要因のランク

行列の右対角要素の合計を計算する Python プログラム 行列の右対角要素の合計を計算する Python プログラム Aug 19, 2023 am 11:29 AM

人気のある汎用プログラミング言語は Python です。デスクトップ アプリケーション、Web 開発、機械学習など、さまざまな業界で使用されています。幸いなことに、Python には初心者に適したシンプルで理解しやすい構文があります。この記事では、Python を使用して行列の右対角の合計を計算します。マトリックスとは何ですか?数学では、数学的オブジェクトまたはそのプロパティを記述するために長方形の配列または行列を使用します。これは、行と列に配置された数値、記号、または式を含む長方形の配列または表です。例: -234512367574 したがって、これは 3 行 4 列の行列であり、3*4 行列として表されます。さて、行列には​​ 2 つの対角線、主対角線と副対角線があります。

合計スコアとパーセンテージを計算する Java プログラムの例 合計スコアとパーセンテージを計算する Java プログラムの例 Sep 11, 2023 pm 06:01 PM

Java プログラムを使用して合計スコアとパーセンテージを計算する方法を示します。合計スコアは利用可能なすべてのスコアの合計を指しますが、パーセンテージという用語は、計算されたスコアを合計スコアで割って、結果の数値 100 を掛けたものを指します。 percentage_of_marks=(obtained_marks/total_marks)×100 例 1 これは、合計スコアとパーセンテージを計算する方法を示す Java プログラムです。 //Totalmarks と Percentagecalculated をデモンストレーションする Java プログラムimportjava.io.*;publicclassTotalMarks_

See all articles