Definition:Decision Problem
Jump to navigation
Jump to search
Definition
Let $\FF$ be a formal system.
The decision problem for $\FF$ is the question as to whether or not there exists an effective procedure for determining whether or not a given well-formed formula of $\FF$ is a theorem of $\FF$.
That is, whether $\FF$ is decidable.
Also see
- Results about decision problems can be found here.
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): decidable
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): decision problem
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): decidable
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): decision problem