[Solved]: What is the exact meaning of a Predicate, decidability and computability?

Problem Detail: 

In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as:

By a predicate or a Boolean-valued function on a set $S$ we mean a total function $P$ on $S$ such that for each $a \in S$, either $P(a) = True$ or $P(a)=False$.

So every predicate is a total function. in Page 30 he says:

• A given partial function $g$ (of one or more variables) is said to be partially computable if it is computed by some program
• A function is said to be computable if it is both partially computable and total.

in page 68 he says:

Theorem 2.1. $HALT(x, y)$ is not a computable predicate.

Since every predicate is total, so the only reason which causes this theorem to be true is that there must be no program that computes $HALT(x,y)$, it means $HALT(x,y)$ is not a partially computable, if it was then it would be computable because it is total!

Not that in page 76 the writer says:

Note that a partially computable predicate is necessarily computable

In this link I found two statements that seems to be a contradiction.

• In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turing-acceptable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
• The Halting problem is recursively enumerable but not recursive.

I know that decidability terminology is used for sets but computability terminology is used for languages. if we can say that recursively enumerable sets are partially computable (= partially deciable) then Since Halting problem is r.e. so it is partially computable. If it is partially computable and since it is total so Halting problem must be computable !!!

Asked By : Drupalist

Answered By : Yuval Filmus

There is an unfortunate clash of terminology here. Before exposing it, let me just mention that decidable and computable are synonyms. You mention several concepts, including:

1. Partially computable: A partial function which is computed by some program that doesn't necessarily always halt.
2. Partially decidable (terminology I personally have never heard): A language (i.e. set of words) that is enumerated by some program.

These are different concepts. Partial computability is a property of (partial) functions. Since languages can also be viewed as predicates, partial computability can also apply to languages, though this is somewhat misleading, since a partially computable predicate is always computable.

Partial decidability, usually known by some of the other names you mention, is a property of languages. Partial decidability can also apply to predicates by considering the language of all input tuples satisfying the predicate.

The halting problem itself has many variants, of which you mention two:

1. The halting predicate $HALT(x,y)$, true if the program encoded by $x$ halts on input $y$.
2. The halting problem, which is the language of all pairs $(x,y)$ such that the program encoded by $x$ halts on input $y$.

The halting problem is a language whose corresponding predicate is the halting predicate. Both are partially decidable but not partially computable or computable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37606