reductions


I've been having some problems with this.

first of all.

~hp = {<m,x> | m is a turing machine that does not halt on x}

~hp is not r.e. If I am given any language A that is not r.e. Should
it be easy to reduce ~HP to A ?

Some books imply that if you are reducing X to Y, Y should be simpler,
but on the other hand sometimes you want to show Y is not r.e. or
decidable, in that case you pick X that is not r.e or decidable, for
that situation does X need to be simpler ? Or what does it mean to be
simpler ?

The hello world tested in the Hopcroft, Ullman automata theory book on
page 324 is an example of reducing H to H2 ?

I was given the following homework problem:

let A = {<M,x> | M is a turing machine and on input x outputs the
reverse of x}
show that A is r.e. but not decidable.

It seems to me that it is only r.e. up to a given size of the input.
Suppose you can test all possible strings for x up to length 1 million.
Isn't it possible at 1 trillion someplace that M will not reverse it's
input ? Since the size of the input is potentially infinite, how can
you ever be sure a given program allways will reverse it's input even
if it has for many such input ? I used the method in the Ullman book
page 324 to show it was not decidable, though perhaps there was a
simpler way ?

.

Relevant Pages

  • Re: what does "serialization" mean?
    ... one never "creates" language, ... of any sort but by "generally accepted usage". ... >> It is in fact correct to say that the palindrome of a string is its ... >> reverse, and that a palindromic string is identical to its ...
    (comp.programming)
  • Re: reversing a byte
    ... Whence this unhealthy fascination with "most efficient?" ... to reverse a byte. ... The C language says nothing about the ... forum for such questions. ...
    (comp.lang.c)
  • Re: Two questions
    ... language can "easily" be reverse-engineered in the same way, with the only difference being the degree of ease involved. ... If the code is worth enough to someone that they are willing to risk violating your license terms, they *will* be able to recover enough source code to do what they need. ... Don't intend to hijack this thread, ... I know several accomplished C/assembly programmers who have told me that reverse engineering object code from either of these two languages is anything but trivial. ...
    (comp.lang.python)
  • Re: Question about Descriptors
    ... >>to learn the language. ... >>interesting, REVERSE, which reverses the characters in a string. ... >>Not wanting to start a war with those who believe in declaring all variables, ... and COMMON blocks of GLOBAL data can be declared in ...
    (comp.os.vms)
  • Re: Question about Descriptors
    ... > interesting, REVERSE, which reverses the characters in a string. ... or did you mean to re-use the B$ in your mainline program that ... Or are some language better suited for small independant programs? ...
    (comp.os.vms)