Difference between revisions of "Decidable set"
(Importing text file) |
(TeX done) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | A set of | + | A set of [[constructive object]]s of some fixed type which admits an [[algorithm]] for checking whether an element belongs to it. In fact one can restrict oneself to the concept of a decidable set of natural numbers, since the more general case can be reduced to this case by enumerating the objects under consideration. A set $M$ of natural numbers is said to be decidable if there exists a [[general recursive function]] $f$ such that $M = \{ n : f(n) = 0 \}$. In this case $f$ is an algorithm for checking whether a natural number belongs to $M$: indeed, $n \in M$ is equivalent to $f(n) = 0$. A decidable set of natural numbers is also often called a general recursive set or a recursive set. |
− | In many well-known mathematical problems (such as the word identity problem, the homeomorphism problem, Hilbert's 10th problem, the "Entscheidungsproblem" in mathematical logic) one is required to prove or refute the assertion that a certain concrete set is decidable. Well-known (negative) solutions to the problems listed above consist of establishing that the sets corresponding to them are undecidable (see also [[ | + | In many well-known mathematical problems (such as the word identity problem, the homeomorphism problem, Hilbert's 10th problem, the "Entscheidungsproblem" in mathematical logic) one is required to prove or refute the assertion that a certain concrete set is decidable. Well-known (negative) solutions to the problems listed above consist of establishing that the sets corresponding to them are undecidable (see also [[Algorithmic problem]]). |
====References==== | ====References==== | ||
− | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)</TD></TR></table> | + | <table> |
+ | <TR><TD valign="top">[1]</TD> <TD valign="top"> E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)</TD></TR> | ||
+ | </table> | ||
====Comments==== | ====Comments==== | ||
+ | Decidable sets are also referred to as ''recursive'' or ''solvable''. ([a3], p.11) | ||
+ | ====References==== | ||
+ | <table> | ||
+ | <TR><TD valign="top">[a1]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165</TD></TR> | ||
+ | <TR><TD valign="top">[a2]</TD> <TD valign="top"> S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951) pp. 288</TD></TR> | ||
+ | <TR><TD valign="top">[a3]</TD> <TD valign="top"> William I. Gasarch, Georgia Martin, "Bounded Queries in Recursion Theory", Progress in Computer Science and Applied Logic '''16'''. Springer (1999) ISBN 0817639667</TD></TR> | ||
+ | </table> | ||
− | + | {{TEX|done}} | |
− |
Revision as of 22:37, 10 January 2016
A set of constructive objects of some fixed type which admits an algorithm for checking whether an element belongs to it. In fact one can restrict oneself to the concept of a decidable set of natural numbers, since the more general case can be reduced to this case by enumerating the objects under consideration. A set $M$ of natural numbers is said to be decidable if there exists a general recursive function $f$ such that $M = \{ n : f(n) = 0 \}$. In this case $f$ is an algorithm for checking whether a natural number belongs to $M$: indeed, $n \in M$ is equivalent to $f(n) = 0$. A decidable set of natural numbers is also often called a general recursive set or a recursive set.
In many well-known mathematical problems (such as the word identity problem, the homeomorphism problem, Hilbert's 10th problem, the "Entscheidungsproblem" in mathematical logic) one is required to prove or refute the assertion that a certain concrete set is decidable. Well-known (negative) solutions to the problems listed above consist of establishing that the sets corresponding to them are undecidable (see also Algorithmic problem).
References
[1] | E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964) |
Comments
Decidable sets are also referred to as recursive or solvable. ([a3], p.11)
References
[a1] | H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165 |
[a2] | S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951) pp. 288 |
[a3] | William I. Gasarch, Georgia Martin, "Bounded Queries in Recursion Theory", Progress in Computer Science and Applied Logic 16. Springer (1999) ISBN 0817639667 |
Decidable set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Decidable_set&oldid=15318