How do you prove that there exist two languages A and B that are
Turing-incomparable, that is A is not Turing-reducible to B and B is
not Turing-reducible to A?

---

Request for Question Clarification by mathtalk-ga on 25 Jul 2004 20:26 PDT

Hi, nr9-ga:

Post's original formulation of the problem was in terms two
recursively enumerable sets A,B, neither of which is recursive in the
other.  The problem was solved independently by Russian A.A. Muchnik
(1956) and by R.M. Friedberg (1957) using essentially the same
approach, the "priority" or "finite injury" method.

Are you interested in an exposition of this method of proof?  Is the
context of "languages" versus sets of positive integers significant
for your purpose?

regards, mathtalk-ga

---

Clarification of Question by nr9-ga on 25 Jul 2004 21:32 PDT

I don't really know a lot of math
I only know the formulation of the problem in terms of the languages.

I dont know what priority or finite injury is...

I'm interested in seeing a step by step proof that I can understand.

my background in math is lower division undergraduate math, including
discrete math. i have taken an undergraduate algorithms course.

---

Request for Question Clarification by mathtalk-ga on 25 Jul 2004 23:09 PDT

Hi, nr9-ga:

See if these are your terms of reference for this problem.

A formal language is said to be decidable (or recursive, or
Turing-computable) if there is an algorithm (Turing machine, for the
sake of concreteness) which always halts with YES or NO after a finite
number of steps according to whether the input string is or is not
valid in the language.  The number of steps, though always finite for
each input, need not be bounded in any specific way related to the
size of the input.

A formal language is said to be partly decidable (or recursively
enumerable, or Turing-recognizable) if there is an algortithm (again,
epitomized as a Turing machine) that always halts with YES if and only
if the input string is valid in the language.  If the input string is
not valid in the language the algorithm/Turing machine with either
halt with NO or never halt.

Given two languages that are each Turing-recognizable, one can define
(as Turing did) a relationship between them involving Oracle Turing
machines.  That is, we say language A is Turing-reducible to language
B if language A is decidable by a generalized Turing machine that has
"oracular" knowledge of language B.  In other words there is an
instruction that can decide in one step if an input is or is not valid
in language B, such a capability being referred to as an "oracle".

It was shown by Turing that the halting problem is in effect a
partially decidable language, for we input the Turing program and wait
for the Turing machine to halt.  If it does, then the answer is YES. 
But if it doesn't halt, then we never get an answer because we are
still waiting.

Furthermore this "language" of the halting problem is Turing-complete
in the sense that every Turing-recognizable language is reducible to
the halting problem "language".

The relation of "Turing-reducible to" is shown fairly easily to be a
partial-order on Turing-recognizable languages.  The question that
Post raised in a famous 1944 paper amounts, in the terminology of
"languages", to whether there exists anything in between the
"complete" ones like the halting problem and the "decidable" ones (for
which a Turing machine that always halts exists).

This was proven to be the case by Muchnik and Friedberg
(independently), but their approach like Post's formulation of the
problem, was in terms of decision procedures for a recursively
enumerable set of integers.

The connection with a decision problem for a formal language should be
fairly clear to you.  An input for a Turing machine is prepared using
a preset finite "alphabet" of symbols, excluding  a "blank".  Any such
string can be encoded as an equivalent number, and the decision
problem for the "language" is then equivalent (for any particular
encoding) to a decision procedure for the corresponding recursively
enumerable set of numbers (the ones that result from encoding valid
strings).

If this is _not_ consistent with the problem you intended to ask
about, please advise me of where I've misunderstood the Question. 
Otherwise let me know the problem is the same as the one you are
concerned with, and hopefully I or another researcher will be able to
accomodate you.

regards, mathtalk-ga

---

Clarification of Question by nr9-ga on 26 Jul 2004 02:05 PDT

yeah, well, i dont need the answer to Post's problem

it is sufficient to show that "is Turing reducible" is a partial order

---

Clarification of Question by nr9-ga on 26 Jul 2004 07:19 PDT

sorry i mean its sufficient to prove that turing reducibility is a
partial order and not a total order

---

Request for Question Clarification by mathtalk-ga on 26 Jul 2004 09:39 PDT

Okay, this is what Muchnik & Friedberg showed, and what you asked
about in the original Question.  That is, exhibit two languages (or
recursively enumerable sets) which are _not_ comparable in the sense
of one being Turing-reducible to the other.

It follows from this that A and B each represent a class of
"undecidability" different from each other and from the classes of
"decidable" and "completely undecidable" languages (or r.e. sets).

This is often termed a "diamond theorem" because it says the following
diamond can be embedded in the partial order R of recursively
enumerable sets:

      K = "completely undecidable" class, eg. halting problem
     / \
    /   \
   A     B
    \   /
     \ /
      0 = "decidable" class, ie. recursive sets

Since A and B are not comparable, the partial order here is not a total order.

I sugggest we proceed to a stage of clarifications and comments to
assess what prelimenaries are needed for you to understand the proof
based on the "priority" method.

regards, mathtalk-ga

---

Clarification of Question by nr9-ga on 26 Jul 2004 09:49 PDT

got that, is understanding "recursively enumerable sets" necessary to
understand the proof?

---

Request for Question Clarification by mathtalk-ga on 26 Jul 2004 13:41 PDT

As a practical matter, yes.

Turing-recognizable language = recursivley enumerable set

Turing-computable language   = recursive set

The distinction is of fundamental importance to the subject, so
perhaps we'll start there in a string of Comments below.  I don't want
to post an Answer until we are within striking range of producing a
proof that you understand "step by step".

regards, mathtalk-ga

---

Clarification of Question by nr9-ga on 26 Jul 2004 17:36 PDT

--> IN COMMENTS

A "language" in the context of this problem means a subset of all
finite strings formed from a preassigned alphabet that are Turing
recognizable, ie. for which a Turing machine will eventually halt with
state YES if and only if the input is a member of that "valid" subset
of strings.

For example, let's suppose our alphabet consists of "0" and "1" as the
only symbols.  You can easily think of the possible inputs as binary
representations of (nonnegative) integers (and this can be immediately
generalized if the alphabet contains N symbols, to representations in
radix N).

Many different subsets of such binary strings are Turing recognizable.
 To suggest a few:

1) the set of all binary strings (take the Turing machine that always
halts with YES)

2) the subset of all binary strings which start with 0, ie. the even
numbers if considered as the least significant bit (take the Turing
machine which examines the first entry and halts with YES if it
contains a 0 or else halts with NO if it contains a 1)

3) the subset of all binary strings which contain no 0's, ie. numbers
of the form 2^m - 1 for m at least 1 (take the Turing machine which
examines each entry starting with the first and halts with NO if it
contains a 0, else advances the tape to the next entry until a blank
is found, in which case the machine halts with YES)

In fact these three examples illustrate languages (or sets) that are
not only recognizable but are actually computable (decidable).  This
is because the machines involved _always_ halt either with YES or NO. 
In terms of sets we say that they are not only recursively enumerable
(from being able to generate a list that eventually mentions each
member of the set) but also recursive.

In fact a good proposition to know is this:

A language is computable (decidable) if and only if there exists both
a Turing machine to recognize strings that belong to the language and
a Turing machine to recognize strings that do not belong.

Stated in terms of sets of numbers, a set is recursive if and only if
both the set and its complement are recursively enumerable.

This is a good point to stop and see if there are any issues that need
clarification.

regards, mathtalk-ga


NEXT:  An example of a language which is recognizable but not
computable (a set of numbers that is recursively enumerable but whose
complement is not).

hi, i just don't understand the terms recursive and recursively enumerable

i kno the next one which would be A_TM or something like that

Can you think of some equivalent terms that you may know?

A rather pedantic effort (IMHO) has been made to replace "recursive
sets" with "computable sets" and "recursively enumerable (r.e.) sets "
with "computably enumerable (c.e.) sets".  Perhaps these are familiar?

If not, you can learn them.  These are indisputably the fundamental
notions to understanding the subject at hand.

regards, mathtalk-ga

I just kno Turing-decidable and Turing-recognizable
is that the same thing?

or do  i need to understand why they are also called recursive and
recursively enumerable?

i also kno that a decidable language can be enumerated in lexicographic order
and that a recognizable language can be enumerated

Okay, that's the ticket.  The idea is that to be decidable requires
that both the language and its antithesis (the set complement) are
recognizable.

You see, if the "recognizable language" could be enumerated, not just
in some random order but in specifically lexicographic order, then we
could watch the list as it is given in order to see whether or not a
particular "word" appears in the output.

Since the output is assumed in lexicographic order, either the word
does appear in the list where we expect it, or else the list goes
merrily on past that point (which tells us the word is definitely
_not_ going to appear).

So every decidable language is recognizable, but the converse is not true.

To show this involves a discussion of the halting problem for Turing
machines, and an appeal to the notion of a "universal" Turing machine.

The concept of a Turing machine will seem, certainly to those with
experience in programming real computers, to be artificially
frustrating.  It works a square at a time on a one-dimensional tape of
indefinite length, going forward or backward as determined by its
state and the contents of the current square (all of which is or could
be expressed as a lookup table).

But the purpose of using such an artificially simple "engine" for
computation is to make clear that any Turing machine, together with
its initial state and input, can be defined by a suitably constructed
"word" in an alphabet specifically designed for the purpose of
creating a "universal" Turing machine.

The universal Turing machine takes as input the "definition" of any
other Turing machine (together with a simulated initial state and
simulated input) and proceeds to "compute" all the subsequent actions
of that Turing machine.  This was the idea that Turing put to use in
solving Hilbert's Entscheidungsproblem (the decidability problem for
first order logic).

Turing asks and answers a related question, which then turns out to be
the key to solving Hilbert's question.  He asks if there is Turing
machine M that can recognize the "language" (definitions in the
special alphabet mentioned above for a universal Turing machine) of
Turing machines (plus their initial states and inputs) that never
halt.

If we claim there is such a Turing machine, then without loss of
generality we can assume that the machine will halt if and only if the
answer is YES (that the input describes a machine that never halts) by
a minor tweak to the symbol/state lookup table.

Turing asks us to consider what would happen when this machine is
given the appropriate initial state and the input word that describes
this machine and that state together with that input.  It sounds
circular, but if such a machine exists, then so would the description
of it.

Now the Turing machine M given this input will either halt or not.  If
it halts, that means (according to the claim made for M above) that it
should not halt.  If it does not halt, that means (again, according to
the claim) that it should!

This contradiction implies no such Turing machine is possible.  Thus
the language of "Turing machines that never halt" is unrecognizable.

But the language of "Turing machines to do halt" is recognizable!  For
this we simply need the universal Turing machine.  We feed it the
description of a Turing machine and so forth, and the universal Turing
machine will halt (by its simulation of that) if and only if the
described Turing machine will halt.

Thus we have an example of a recognizable language whose complement is
not recognizable, or as we explained at the outset of this Comment, a
recognizable language which is not decidable (aka not computable, aka
not recursive).

Questions?

regards, mathtalk-ga


NEXT:  Turing-reducibility induces a partial order on equivalence
classes of languages (degrees of undecidability).

i already know the stuff you just posted...

sorry for the attitude, but i just got annoyed that I did not get any
new information out of the past few comments

i realize that you didn't know what I knew but its pretty safe to
assume that I knew what the terms in the question meant.

please continue as the next stuff would probably be deeper and helpful

An "oracle" for language A is a "black box" that can decide language A
(accepting or rejecting an input word as belonging or not to A) in a
single step, and an oracle Turing machine is a Turing machine that can
use access to such an oracle in addition to all the other features of
a Turing machine.

One arrangement considers that the Turing machine prints the input for
the oracle on its own tape, then calls the oracle to have that input
evaluated:

[Oracle machine]
http://www.campusprogram.com/reference/en/wikipedia/o/or/oracle_machine.html

Another arrangement considers that the Turing machine is equipped with
a second tape for the oracle operation:

[oracle Turing machine]
http://www.nist.gov/dads/HTML/oracleTur.html

In any case we will say that language B is (Turing-)reducible to A if
a Turing machine equipped with an oracle for A can decide language B. 
For convenience we write:

B <~ A

Note that the direction here is from "harder" language A down to
"easier" language B, even though the phrase "reducible to" might lead
one to point the arrow in the other direction.

We need to establish that this relationship is a transitive one, ie.
if language B is reducible to A, and language C is reducible to B,
then language C is also reducible to A:

B <~ A  and  C <~ B  implies  C <~ A

This can be argued informally by replacing the use of an oracle for B
in deciding C (as the second relation allows) with the use of an
oracle Turing machine for deciding B given an oracle for A (as the
first relation allows).  Thus we obtain an oracle Turing machine that
decides C from an oracle for A, as the third relation requires.

Despite the transitivity of this relation, it is not itself a
partial-order on languages.  One must define equivalence classes of
languages, ie.

languages A,B are Turing equivalent
    <==>    A is reducible to B and B reducible to A

Note that there are other notions of reducibility, such as many-one
reducible, but because we are only going to discuss
Turing-reducibility, I've taken the liberty of shortening the
terminology.

Now the relation <~ on (formal) languages induces a partial-order on
these equivalence classes of (mutually reducible) languages.  The
equivalence classes themselves are often referred to as "degrees (of
undecidability)".

For example, the induced relationship:

 {B} < {A}
     -

on the equivalence classes of languages A,B from B <~ A, together with
the reverse relationship from A <~ B, is enough to show equality of
the two "degrees" or equivalence classes:

 {A} = {B}

even though the languages A and B are not themselves "equal" in any sense.

Questions?

regards, mathtalk-ga

no questions, please continue :-)