Welcome Guest Search | Active Topics | Members | Log In

Entscheidungsproblem Options
Posted: Friday, May 18, 2018 9:51:17 PM
Rank: Advanced Member
Groups: Member

Joined: 4/15/2008
Posts: 8,895
Points: 19,413



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.[1] The problem 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[2] showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notion 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.

Users browsing this topic

Forum Jump
You cannot post new topics in this forum.
You cannot reply to topics in this forum.
You cannot delete your posts in this forum.
You cannot edit your posts in this forum.
You cannot create polls in this forum.
You cannot vote in polls in this forum.

Main Forum RSS : RSS

SoClean Theme Created by Jaben Cargman (Tiny Gecko)
Powered by Yet Another Forum.net version (NET v2.0) - 11/14/2007
Copyright © 2003-2006 Yet Another Forum.net. All rights reserved.
This page was generated in 0.030 seconds.