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


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.

  • $\begingroup$ The sentence you mention Partial decidability, usually known by some of the other names you mention, is a property of languages. I guess Partial decidability is a property of sets not the languages, right? Is there any relationship between Partial decidability and Partially computable terminologies? $\endgroup$ – No one Jan 26 '15 at 6:06
  • $\begingroup$ @Drupalist: In this context, a language is (no more than) a set of strings. $\endgroup$ – reinierpost Jan 26 '15 at 10:05
  • $\begingroup$ There's no relation whatsoever between partial decidability and partial computability. The names are similar by chance because both concepts are about some aspect of computability. $\endgroup$ – Yuval Filmus Jan 26 '15 at 16:08
  • $\begingroup$ @reinierpost: then both the decidability and computability terminologies are applicable to sets, right? because a language is a set. $\endgroup$ – No one Jan 27 '15 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.