 View Question
Q: Post's Problem ( No Answer,   9 Comments ) Question
 Subject: Post's Problem Category: Computers > Algorithms Asked by: nr9-ga List Price: \$50.00 Posted: 25 Jul 2004 09:34 PDT Expires: 01 Aug 2004 18:45 PDT Question ID: 378814
 ```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` There is no answer at this time. Subject: Re: Post's Problem From: mathtalk-ga on 26 Jul 2004 14:13 PDT
 ```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).```
 Subject: Re: Post's Problem From: nr9-ga on 26 Jul 2004 16:27 PDT
 ```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```
 Subject: Re: Post's Problem From: mathtalk-ga on 26 Jul 2004 17:29 PDT
 ```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```
 Subject: Re: Post's Problem From: nr9-ga on 26 Jul 2004 17:39 PDT
 ```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```
 Subject: Re: Post's Problem From: mathtalk-ga on 26 Jul 2004 18:57 PDT
 ```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).```
 Subject: Re: Post's Problem From: nr9-ga on 26 Jul 2004 19:46 PDT
 `i already know the stuff you just posted...`
 Subject: Re: Post's Problem From: nr9-ga on 27 Jul 2004 16:13 PDT
 ```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```
 Subject: Re: Post's Problem From: mathtalk-ga on 28 Jul 2004 05:00 PDT
 ```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```
 Subject: Re: Post's Problem From: nr9-ga on 28 Jul 2004 09:46 PDT
 `no questions, please continue :-)`
 Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service. If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you. 