post's correspondence problem
- From: yarden.katz@xxxxxxxxx
- Date: 22 Jun 2006 11:15:58 -0700
hi all,
i have two questions about post's correspondence problem. the problem
is as follows: given two lists of strings, a1,...,an and b1,...,bn, the
question is whether there is an ordering (i1,...in) where 1 <= ij <= in
that makes the two lists equal (i.e. represent the same string when
concatenated).
my questions are:
1) why is this undecidable? in other words why can't be just enumerate
all the permutations of the two lists, since both lists are finite, and
check whether any of them make the two lists the same? i really don't
see the undecidability of the question: "given two lists as above, do
they have a solution?" i was hoping someone could explain what causes
it.
2) i know that many people try to show that a certain problem or
formalism is undecidable by showing post's correspondence problem can
be expressed in it. my question is: how is this done, given that
strings are needed? in other words, FOL (w/o equality) is undecidable,
so surely this problem can be expressed in it.. but how can this be
done without expressing strings somehow? can someone show how one might
formalize this problem in FOL w/o equality as an example?
thanks very much. -p
.
- Follow-Ups:
- Re: post's correspondence problem
- From: H. J. Sander Bruggink
- Re: post's correspondence problem
- Prev by Date: Re: Torkel Franzén is dead
- Next by Date: Re: Torkel Franzén is dead
- Previous by thread: When does p imply q?
- Next by thread: Re: post's correspondence problem
- Index(es):
Relevant Pages
|
