翻訳と辞書
Words near each other
・ チューリヒ美術館
・ チューリヒ芸術大学
・ チューリヒ音楽大学
・ チューリヒ音楽院
・ チューリャ型魚雷艇
・ チューリン
・ チューリング
・ チューリングジャンプ
・ チューリングテスト
・ チューリングマシン
チューリングマシンの停止問題
・ チューリングマシーン
・ チューリング・テスト
・ チューリング・パターン
・ チューリング・マシン
・ チューリング・マシーン
・ チューリング完全
・ チューリング機械
・ チューリング次数
・ チューリング賞


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

チューリングマシンの停止問題 : ミニ英和和英辞書
チューリングマシンの停止問題[だい]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [ちょうおん]
 (n) long vowel mark (usually only used in katakana)
: [てい]
 (n) stopping
停止 : [ていし]
  1. (n,vs) suspension 2. interruption 3. stoppage 4. ban 5. standstill 6. deadlock 7. stalemate 8. abeyance 
: [もん]
 【名詞】 1. problem 2. question 
問題 : [もんだい]
 【名詞】 1. problem 2. question 
: [だい]
  1. (n,vs) title 2. subject 3. theme 4. topic 

チューリングマシンの停止問題 ( リダイレクト:停止性問題 ) : ウィキペディア日本語版
停止性問題[ていしせいもんだい ていしもんだい]
計算可能性理論において停止(性)問題(ていしせいもんだい・ていしもんだい、halting problem)は、あるチューリング機械(≒コンピュータプログラムアルゴリズム)が、そのテープのある初期状態(≒入力)に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。
== 概要 ==
プログラム''A''にデータ''x''を入力して実行する事を''A''(''x'')と書き、''A''(''x'')が''y''を出力するとき''y''=''A''(''x'')と書く。コンピュータではいかなるデータも0と1の数字で表し、したがってプログラム自身も0と1の数字で表せる。 コンピュータ用語ではこの数値化を「符号化」と呼び、理論計算機科学では「ゲーデル数化」という。以下記号を簡単にする為、プログラムAを数字で表したものも、Aと書く。 よって例えばプログラムA、Bに対し、「A(B)」は、「プログラムBを表す数字をBとし、AにBを入力して実行する」の意である。停止性問題とは、「プログラムAとデータxが与えられたとき、A(x)が停止するかどうかを決定せよ」という問題である。
また「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。 すなわち以下の性質を満たすプログラム''H''は存在しない、という定理である。
全てのプログラム''A''と全てのデータ''x''に対し、
* ''A''(''x'')の実行は停止する ⇒ ''H''(''A'',''x'')はYESを出力する。
* ''A''(''x'')の実行は停止しない ⇒ ''H''(''A'',''x'')はNOを出力する。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「停止性問題」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Halting problem 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.