Entscheidungsproblem

tipo de documento Wikipedia Artikulua DbpediaThing

Equipo Didactalia

Gustatzen zait 0
Bisitak 7
Oharrak 0
Hemen gorde:
Ekintzak
- Lotura bidali

Baliabide honi buruz...

Entscheidungsproblem

DbpediaThing

Artículo WikipediaFuente Dbpedia

In mathematics and computer science, the Entscheidungsproblem (pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for 'decision problem') is a challenge posed by David Hilbert in 1928.[citation needed] The Entscheidungsproblem asks for an algorithm that takes as input a statement of a first-order logic (possibly with a finite number of axioms beyond the usual axioms of first-order logic) and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.In 1936, Alonzo Church and Alan Turing published independent papers showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notation of "effectively calculable" is captured by the functions computable by a Turing machine (or equivalently, by those expressible in the lambda calculus). This assumption is now known as the Church–Turing thesis.

Wikipedia Inglés http://en.wikipedia.org/wiki/Entscheidungsproblem

Wikipedia Español http://es.wikipedia.org/wiki/Entscheidungsproblem

Enlaces externos relacionado http://plms.oxfordjournals.org/cgi/reprint/s2-42/1/230 http://www.abelard.org/turpap2/tp2-ie.asp http://www.turingarchive.org/browse.php/B/12