Church-Turing thesis

/tʃɜːrtʃ ˈtʊərɪŋ ˈθiːsɪs/ チャーチ＝チューリング・テーゼ

1. 任意のアルゴリズム的に計算可能な関数は、チューリングマシンによって計算可能であるという提唱。

コンピュータ科学における最も重要な提唱の一つで、人間が直観的に「計算可能である」と考える全ての操作は、チューリングマシンという抽象的なモデルで実行できる、という考え方を示します。これは、アルゴリズムの能力の限界を理解する上で不可欠な概念です。

The Church-Turing thesis states that any function computable by an algorithm can be computed by a Turing machine. (チャーチ＝チューリングのテーゼは、アルゴリズムによって計算可能なあらゆる関数は、チューリングマシンによって計算可能であると述べている。)

• The Church-Turing thesis: コンピュータ科学における基本的な提唱である「チャーチ＝チューリングのテーゼ」を指します。
• states that: 「～と述べている」という意味で、ある事実や原則を表明する際に使われます。
• any function computable by an algorithm: アルゴリズムによって計算できる、任意の関数を意味します。
• can be computed by a Turing machine: チューリングマシンという仮想的な機械によって計算可能である、という可能性を示します。

This thesis provides a fundamental concept in computability theory. (このテーゼは、計算可能性理論における基本的な概念を提供する。)

• This thesis: 直前の文脈で言及された「チャーチ＝チューリングのテーゼ」を指します。
• provides: 「提供する」「与える」という意味の動詞です。
• a fundamental concept: 「基本的な概念」という意味で、ある分野の根幹をなす考え方を指します。
• in computability theory: 「計算可能性理論」という数学的・コンピュータ科学的分野を指します。

Its implications extend to the limits of what computers can and cannot do. (その示唆は、コンピュータができることとできないことの限界にまで及ぶ。)

• Its implications: 「その示唆」という意味で、チャーチ＝チューリングのテーゼが持つ影響や結果を指します。
• extend to: 「～まで及ぶ」「～に広がる」という意味で、影響や範囲の拡大を示します。
• the limits of: 「～の限界」という意味で、ある能力や範囲の境界を指します。
• what computers can and cannot do: 「コンピュータができることとできないこと」という、コンピュータの能力の範囲を具体的に示します。

The Church-Turing thesis is central to theoretical computer science. (チャーチ＝チューリングのテーゼは、理論計算機科学において中心的な役割を果たす。)

• The Church-Turing thesis: この文の主語で、特定の科学的提唱を指します。
• is central to: 「～にとって中心的である」という意味で、非常に重要であることを示します。
• theoretical computer science: コンピュータの理論的な側面を探求する学問分野を指します。

関連

• Turing machine
• Alonzo Church
• Alan Turing
• Computability theory
• Algorithm
• Effective calculability
• Halting problem