英和和英

出典:『Wikipedia』 (2011/06/21 12:47 UTC 版)

英語による解説

引用

In mathematics, the Entscheidungsproblem (pronounced [ɛntˈʃaɪdʊŋspʁoˌbleːm], German for 'decision problem') is a challenge posed by David Hilbert in 1928. The Entscheidungsproblem asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false. The algorithm need not justify its answer, nor provide a proof, so long as it is always correct. Such an algorithm would be able to decide, for example, whether statements such as Goldbach's conjecture or the Riemann hypothesis are true, even though no proof or disproof of these statements is known. The Entscheidungsproblem has often been identified in particular with the decision problem for first-order logic (that is, the problem of algorithmically determining whether a first-order statement is universally valid).