Namespaces
Variants
Actions

Difference between revisions of "Decidable predicate"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
(Category:Logic and foundations)
 
Line 1: Line 1:
 
{{TEX|done}}
 
{{TEX|done}}
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|computable function]].
+
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|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" .
+
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 [[Decidable set|decidable set]].
+
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.

How to Cite This Entry:
Decidable predicate. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Decidable_predicate&oldid=31759
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article