Difference between revisions of "Decidable predicate"
(TeX) |
(Category:Logic and foundations) |
||
Line 1: | Line 1: | ||
{{TEX|done}} | {{TEX|done}} | ||
− | An -place predicate P given on a certain set of constructive objects (for example, natural numbers) M for which there exists an algorithm which enables one to find the value (T or F) of P on any n-tuple a_1,\ldots,a_n of elements in M. In other words, a predicate is decidable if, regarded as an n-place function on M with values in the set \{\text T,\text F\}, it is a [[ | + | An n-place predicate P given on a certain set of constructive objects (for example, natural numbers) M for which there exists an algorithm which enables one to find the value (T or F) of P on any n-tuple a_1,\ldots,a_n of elements in M. In other words, a predicate is decidable if, regarded as an n-place function on M with values in the set \{\text T,\text F\}, it is a [[computable function]]. |
− | When the concept of a [[ | + | When the concept of a [[recursive function]] or some equivalent concept is used as a mathematical refinement of the concept of computability, then the term "recursive predicate" is usually employed instead of "decidable predicate" . |
====Comments==== | ====Comments==== | ||
− | So, P is a decidable predicate if the set of n-tuples on which P takes the value T (true) is a [[ | + | So, P is a decidable predicate if the set of n-tuples on which P takes the value T (true) is a [[decidable set]]. |
+ | |||
+ | [[Category:Logic and foundations]] |
Latest revision as of 18:17, 9 November 2014
An n-place predicate P given on a certain set of constructive objects (for example, natural numbers) M for which there exists an algorithm which enables one to find the value (T or F) of P on any n-tuple a_1,\ldots,a_n of elements in M. In other words, a predicate is decidable if, regarded as an n-place function on M with values in the set \{\text T,\text F\}, it is a computable function.
When the concept of a recursive function or some equivalent concept is used as a mathematical refinement of the concept of computability, then the term "recursive predicate" is usually employed instead of "decidable predicate" .
Comments
So, P is a decidable predicate if the set of n-tuples on which P takes the value T (true) is a decidable set.
Decidable predicate. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Decidable_predicate&oldid=31759