Mixing
PCP undecidability
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here:
https://en.wikipedia.org/wiki/Post_correspondence_problem
I'll assume whoever will answer the question will be familiar with this proof.
I have seen this proof elsewhere and this kind of proof always mentions that if the $TM M$ halts we can solve the instance of the PCP. So far so good.
Now I was thinking about the case when the $TM M$ does not halt on input $w$.
Then out total number of tuples/pairs ($small(a_i,b_i)$, which get passed onto the PCP) should be countably infinite.
How can we even try to solve the PCP at this point ? Or do we implicitly think: "Thats impossible !" and say "There is no solution!" ?
This part confuses me very much because for the case that the TM halts we construct such a complex method and it seemed "cheap" to just throw the towel for the case when it would not halt.
I hope I could make my thoughts understandable, without much formality.
Any help is appreciated.
reductions undecidability
asked Aug 7 at 19:14
zython
217110
add a comment |Â
up vote
3
down vote
favorite
There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here:
https://en.wikipedia.org/wiki/Post_correspondence_problem
I'll assume whoever will answer the question will be familiar with this proof.
I have seen this proof elsewhere and this kind of proof always mentions that if the $TM M$ halts we can solve the instance of the PCP. So far so good.
Now I was thinking about the case when the $TM M$ does not halt on input $w$.
Then out total number of tuples/pairs ($small(a_i,b_i)$, which get passed onto the PCP) should be countably infinite.
How can we even try to solve the PCP at this point ? Or do we implicitly think: "Thats impossible !" and say "There is no solution!" ?
This part confuses me very much because for the case that the TM halts we construct such a complex method and it seemed "cheap" to just throw the towel for the case when it would not halt.
I hope I could make my thoughts understandable, without much formality.
Any help is appreciated.
reductions undecidability
asked Aug 7 at 19:14
zython
217110
1
The total number of tile pairs is always finite. I suggest reading a formal account, for example in Sipser's textbook.
– Yuval Filmus
Aug 7 at 19:22
@YuvalFilmus I actually have a copy of Sipser, do you mind giving a reference, because while I have not rigorously studied the proof in sipser I never saw anything about the case where the TM does not halt
– zython
Aug 7 at 19:30
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here:
https://en.wikipedia.org/wiki/Post_correspondence_problem
I'll assume whoever will answer the question will be familiar with this proof.
I have seen this proof elsewhere and this kind of proof always mentions that if the $TM M$ halts we can solve the instance of the PCP. So far so good.
Now I was thinking about the case when the $TM M$ does not halt on input $w$.
Then out total number of tuples/pairs ($small(a_i,b_i)$, which get passed onto the PCP) should be countably infinite.
How can we even try to solve the PCP at this point ? Or do we implicitly think: "Thats impossible !" and say "There is no solution!" ?
This part confuses me very much because for the case that the TM halts we construct such a complex method and it seemed "cheap" to just throw the towel for the case when it would not halt.
I hope I could make my thoughts understandable, without much formality.
Any help is appreciated.
reductions undecidability
asked Aug 7 at 19:14
zython
217110
There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here:
https://en.wikipedia.org/wiki/Post_correspondence_problem
I'll assume whoever will answer the question will be familiar with this proof.
I have seen this proof elsewhere and this kind of proof always mentions that if the $TM M$ halts we can solve the instance of the PCP. So far so good.
Now I was thinking about the case when the $TM M$ does not halt on input $w$.
Then out total number of tuples/pairs ($small(a_i,b_i)$, which get passed onto the PCP) should be countably infinite.
How can we even try to solve the PCP at this point ? Or do we implicitly think: "Thats impossible !" and say "There is no solution!" ?
This part confuses me very much because for the case that the TM halts we construct such a complex method and it seemed "cheap" to just throw the towel for the case when it would not halt.
I hope I could make my thoughts understandable, without much formality.
Any help is appreciated.
reductions undecidability
asked Aug 7 at 19:14
zython
217110
asked Aug 7 at 19:14
zython
217110
asked Aug 7 at 19:14
zython
217110
asked Aug 7 at 19:14
zython
217110
217110
1
The total number of tile pairs is always finite. I suggest reading a formal account, for example in Sipser's textbook.
– Yuval Filmus
Aug 7 at 19:22
@YuvalFilmus I actually have a copy of Sipser, do you mind giving a reference, because while I have not rigorously studied the proof in sipser I never saw anything about the case where the TM does not halt
– zython
Aug 7 at 19:30
add a comment |Â
1
The total number of tile pairs is always finite. I suggest reading a formal account, for example in Sipser's textbook.
– Yuval Filmus
Aug 7 at 19:22
@YuvalFilmus I actually have a copy of Sipser, do you mind giving a reference, because while I have not rigorously studied the proof in sipser I never saw anything about the case where the TM does not halt
– zython
Aug 7 at 19:30
1
1
The total number of tile pairs is always finite. I suggest reading a formal account, for example in Sipser's textbook.
– Yuval Filmus
Aug 7 at 19:22
The total number of tile pairs is always finite. I suggest reading a formal account, for example in Sipser's textbook.
– Yuval Filmus
Aug 7 at 19:22
@YuvalFilmus I actually have a copy of Sipser, do you mind giving a reference, because while I have not rigorously studied the proof in sipser I never saw anything about the case where the TM does not halt
– zython
Aug 7 at 19:30
@YuvalFilmus I actually have a copy of Sipser, do you mind giving a reference, because while I have not rigorously studied the proof in sipser I never saw anything about the case where the TM does not halt
– zython
Aug 7 at 19:30
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
An instance of PCP consists of a finite list of tiles. The proof that PCP is undecidable consists of a computable reduction $f$ with the following properties:
- The input to $f$ is a Turing machine $M$ and a valid input $w$ to $M$.
- The output of $f$ is an instance of PCP (i.e., a finite list of tiles).
- The PCP instance $f(M,w)$ is a Yes instance iff $M$ halts on $w$.
A further property of the reduction is that the number of tiles depends only on $M$, though the contents of one of the tiles depends on $w$.
Let us denote the tiles by $(a_1,b_1),ldots,(a_n,b_n)$.
When $M$ halts on $w$, there exists a number $N$ and a sequence $i_1,ldots,i_N in 1,ldots,n$ such that $$ a_i_1 a_i_2 ldots a_i_N = b_i_1 b_i_2 ldots b_i_N. $$
When $M$ does not halt on $w$, no such $N$ exists. However, there does exist an infinite sequence $i_1,i_2,ldots$ such that $$ a_i_1 a_i_2 ldots = b_i_1 b_i_2 ldots, $$
where both sides are infinite words. Perhaps this is what you meant by "total number of tiles". The actual number of tiles is always finite, and independent of the input. The number of instances of tiles required to "solve" the PCP instance could be finite or infinite; but we only consider finite solutions as valid.
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
thank you for answering; you understood my question. accepted !
– zython
Aug 8 at 8:06
add a comment |Â
up vote
2
down vote
Then out total number of tuples/pairs ((ai,bi), which get passed onto the PCP) should be countably infinite.
I'm not entirely sure what you are trying to say here, but it sounds like this statement is the flaw in your reasoning. The number of pairs is always finite, regardless of whether the Turing machine halts or doesn't halt. Since you haven't provided any justification for this claim, it's not clear why you think it is true or what your specific confusion is, but this claim is false.
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
An instance of PCP consists of a finite list of tiles. The proof that PCP is undecidable consists of a computable reduction $f$ with the following properties:
- The input to $f$ is a Turing machine $M$ and a valid input $w$ to $M$.
- The output of $f$ is an instance of PCP (i.e., a finite list of tiles).
- The PCP instance $f(M,w)$ is a Yes instance iff $M$ halts on $w$.
A further property of the reduction is that the number of tiles depends only on $M$, though the contents of one of the tiles depends on $w$.
Let us denote the tiles by $(a_1,b_1),ldots,(a_n,b_n)$.
When $M$ halts on $w$, there exists a number $N$ and a sequence $i_1,ldots,i_N in 1,ldots,n$ such that $$ a_i_1 a_i_2 ldots a_i_N = b_i_1 b_i_2 ldots b_i_N. $$
When $M$ does not halt on $w$, no such $N$ exists. However, there does exist an infinite sequence $i_1,i_2,ldots$ such that $$ a_i_1 a_i_2 ldots = b_i_1 b_i_2 ldots, $$
where both sides are infinite words. Perhaps this is what you meant by "total number of tiles". The actual number of tiles is always finite, and independent of the input. The number of instances of tiles required to "solve" the PCP instance could be finite or infinite; but we only consider finite solutions as valid.
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
thank you for answering; you understood my question. accepted !
– zython
Aug 8 at 8:06
add a comment |Â
up vote
3
down vote
accepted
An instance of PCP consists of a finite list of tiles. The proof that PCP is undecidable consists of a computable reduction $f$ with the following properties:
- The input to $f$ is a Turing machine $M$ and a valid input $w$ to $M$.
- The output of $f$ is an instance of PCP (i.e., a finite list of tiles).
- The PCP instance $f(M,w)$ is a Yes instance iff $M$ halts on $w$.
A further property of the reduction is that the number of tiles depends only on $M$, though the contents of one of the tiles depends on $w$.
Let us denote the tiles by $(a_1,b_1),ldots,(a_n,b_n)$.
When $M$ halts on $w$, there exists a number $N$ and a sequence $i_1,ldots,i_N in 1,ldots,n$ such that $$ a_i_1 a_i_2 ldots a_i_N = b_i_1 b_i_2 ldots b_i_N. $$
When $M$ does not halt on $w$, no such $N$ exists. However, there does exist an infinite sequence $i_1,i_2,ldots$ such that $$ a_i_1 a_i_2 ldots = b_i_1 b_i_2 ldots, $$
where both sides are infinite words. Perhaps this is what you meant by "total number of tiles". The actual number of tiles is always finite, and independent of the input. The number of instances of tiles required to "solve" the PCP instance could be finite or infinite; but we only consider finite solutions as valid.
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
thank you for answering; you understood my question. accepted !
– zython
Aug 8 at 8:06
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
An instance of PCP consists of a finite list of tiles. The proof that PCP is undecidable consists of a computable reduction $f$ with the following properties:
- The input to $f$ is a Turing machine $M$ and a valid input $w$ to $M$.
- The output of $f$ is an instance of PCP (i.e., a finite list of tiles).
- The PCP instance $f(M,w)$ is a Yes instance iff $M$ halts on $w$.
A further property of the reduction is that the number of tiles depends only on $M$, though the contents of one of the tiles depends on $w$.
Let us denote the tiles by $(a_1,b_1),ldots,(a_n,b_n)$.
When $M$ halts on $w$, there exists a number $N$ and a sequence $i_1,ldots,i_N in 1,ldots,n$ such that $$ a_i_1 a_i_2 ldots a_i_N = b_i_1 b_i_2 ldots b_i_N. $$
When $M$ does not halt on $w$, no such $N$ exists. However, there does exist an infinite sequence $i_1,i_2,ldots$ such that $$ a_i_1 a_i_2 ldots = b_i_1 b_i_2 ldots, $$
where both sides are infinite words. Perhaps this is what you meant by "total number of tiles". The actual number of tiles is always finite, and independent of the input. The number of instances of tiles required to "solve" the PCP instance could be finite or infinite; but we only consider finite solutions as valid.
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
An instance of PCP consists of a finite list of tiles. The proof that PCP is undecidable consists of a computable reduction $f$ with the following properties:
- The input to $f$ is a Turing machine $M$ and a valid input $w$ to $M$.
- The output of $f$ is an instance of PCP (i.e., a finite list of tiles).
- The PCP instance $f(M,w)$ is a Yes instance iff $M$ halts on $w$.
A further property of the reduction is that the number of tiles depends only on $M$, though the contents of one of the tiles depends on $w$.
Let us denote the tiles by $(a_1,b_1),ldots,(a_n,b_n)$.
When $M$ halts on $w$, there exists a number $N$ and a sequence $i_1,ldots,i_N in 1,ldots,n$ such that $$ a_i_1 a_i_2 ldots a_i_N = b_i_1 b_i_2 ldots b_i_N. $$
When $M$ does not halt on $w$, no such $N$ exists. However, there does exist an infinite sequence $i_1,i_2,ldots$ such that $$ a_i_1 a_i_2 ldots = b_i_1 b_i_2 ldots, $$
where both sides are infinite words. Perhaps this is what you meant by "total number of tiles". The actual number of tiles is always finite, and independent of the input. The number of instances of tiles required to "solve" the PCP instance could be finite or infinite; but we only consider finite solutions as valid.
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
answered Aug 7 at 21:40
Yuval Filmus
181k12171329
181k12171329
thank you for answering; you understood my question. accepted !
– zython
Aug 8 at 8:06
add a comment |Â
thank you for answering; you understood my question. accepted !
– zython
Aug 8 at 8:06
thank you for answering; you understood my question. accepted !
– zython
Aug 8 at 8:06
thank you for answering; you understood my question. accepted !
– zython
Aug 8 at 8:06
add a comment |Â
up vote
2
down vote
Then out total number of tuples/pairs ((ai,bi), which get passed onto the PCP) should be countably infinite.
I'm not entirely sure what you are trying to say here, but it sounds like this statement is the flaw in your reasoning. The number of pairs is always finite, regardless of whether the Turing machine halts or doesn't halt. Since you haven't provided any justification for this claim, it's not clear why you think it is true or what your specific confusion is, but this claim is false.
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
add a comment |Â
up vote
2
down vote
Then out total number of tuples/pairs ((ai,bi), which get passed onto the PCP) should be countably infinite.
I'm not entirely sure what you are trying to say here, but it sounds like this statement is the flaw in your reasoning. The number of pairs is always finite, regardless of whether the Turing machine halts or doesn't halt. Since you haven't provided any justification for this claim, it's not clear why you think it is true or what your specific confusion is, but this claim is false.
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Then out total number of tuples/pairs ((ai,bi), which get passed onto the PCP) should be countably infinite.
I'm not entirely sure what you are trying to say here, but it sounds like this statement is the flaw in your reasoning. The number of pairs is always finite, regardless of whether the Turing machine halts or doesn't halt. Since you haven't provided any justification for this claim, it's not clear why you think it is true or what your specific confusion is, but this claim is false.
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
Then out total number of tuples/pairs ((ai,bi), which get passed onto the PCP) should be countably infinite.
I'm not entirely sure what you are trying to say here, but it sounds like this statement is the flaw in your reasoning. The number of pairs is always finite, regardless of whether the Turing machine halts or doesn't halt. Since you haven't provided any justification for this claim, it's not clear why you think it is true or what your specific confusion is, but this claim is false.
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
answered Aug 7 at 21:00
D.W.♦
95.3k11109255
95.3k11109255
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f96057%2fpcp-undecidability%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
The total number of tile pairs is always finite. I suggest reading a formal account, for example in Sipser's textbook.
– Yuval Filmus
Aug 7 at 19:22
@YuvalFilmus I actually have a copy of Sipser, do you mind giving a reference, because while I have not rigorously studied the proof in sipser I never saw anything about the case where the TM does not halt
– zython
Aug 7 at 19:30