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 !!!