Re: reductions
- From: Patricia Shanahan <pats@xxxxxxx>
- Date: Sun, 26 Nov 2006 02:10:35 GMT
surf wrote:
....
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 ?
Are you sure you are reading the question correctly? The instance is
<M,x> so for any given test you only need to find out if a particular M
is a TM that reverses a particular x.
A is different from:
{<M> | M is a TM and for every input x M outputs the reverse of x}
which I think may be the language you are trying to recognize.
Patricia
.
- References:
- reductions
- From: surf
- reductions
- Prev by Date: [Ann] Programming language research engine (PLRE.org)
- Next by Date: Optimal Partitioning of an Undirected Graph Using Matroids
- Previous by thread: reductions
- Next by thread: [Ann] Programming language research engine (PLRE.org)
- Index(es):
Relevant Pages
|
