

Subject:
Post's Problem
Category: Computers > Algorithms Asked by: nr9ga 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 Turingincomparable, that is A is not Turingreducible to B and B is not Turingreducible to A?  
 
 
 
 
 
 
 
 


There is no answer at this time. 

Subject:
Re: Post's Problem
From: mathtalkga 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, mathtalkga 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: nr9ga 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: mathtalkga 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, mathtalkga 
Subject:
Re: Post's Problem
From: nr9ga on 26 Jul 2004 17:39 PDT 
I just kno Turingdecidable and Turingrecognizable 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: mathtalkga 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 onedimensional 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, mathtalkga NEXT: Turingreducibility induces a partial order on equivalence classes of languages (degrees of undecidability). 
Subject:
Re: Post's Problem
From: nr9ga on 26 Jul 2004 19:46 PDT 
i already know the stuff you just posted... 
Subject:
Re: Post's Problem
From: nr9ga 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: mathtalkga 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 partialorder 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 manyone reducible, but because we are only going to discuss Turingreducibility, I've taken the liberty of shortening the terminology. Now the relation <~ on (formal) languages induces a partialorder 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, mathtalkga 
Subject:
Re: Post's Problem
From: nr9ga on 28 Jul 2004 09:46 PDT 
no questions, please continue :) 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 