Reducing Pcp (Post's correspondence problem) to mPcp
$begingroup$
Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version requires any matching sequence of "dominoes" $p_{i_1}, p_{i_2}, ..., p_{i_m}$ to start with the first "domino", $p_1$.
I am very well aware of the fact that there exists a match for
an instance $I=langle p_1, ..., p_nrangle$ of $Pcp$ if and only if there exists a match for one of the instances $I_1, I_2, ..., I_n$ of $mPcp$ where $I_j=langle p_j, p_{j+1}, ..., p_n, p_1, ..., p_{j-1}rangle$ for $j=1, ..., n$. In other words, if and only if $I$ is a yes-instance for $Pcp$, there is a way to rotate the list of "dominoes" in a cyclic manner such that the starting piece in the found match for $Pcp$ is put in the first position.
However, it is not clear to me how this observation could lead to a mapping from an instance $I$ of $Pcp$ to the "correct" instance $I_j$ of $mPcp$ that can be carried out in a finite amount of steps for any $I$, thus serving as a suitable reduction.
Could anybody point me in the right direction? Thank you very much.
computability
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
$endgroup$
add a comment |
$begingroup$
Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version requires any matching sequence of "dominoes" $p_{i_1}, p_{i_2}, ..., p_{i_m}$ to start with the first "domino", $p_1$.
I am very well aware of the fact that there exists a match for
an instance $I=langle p_1, ..., p_nrangle$ of $Pcp$ if and only if there exists a match for one of the instances $I_1, I_2, ..., I_n$ of $mPcp$ where $I_j=langle p_j, p_{j+1}, ..., p_n, p_1, ..., p_{j-1}rangle$ for $j=1, ..., n$. In other words, if and only if $I$ is a yes-instance for $Pcp$, there is a way to rotate the list of "dominoes" in a cyclic manner such that the starting piece in the found match for $Pcp$ is put in the first position.
However, it is not clear to me how this observation could lead to a mapping from an instance $I$ of $Pcp$ to the "correct" instance $I_j$ of $mPcp$ that can be carried out in a finite amount of steps for any $I$, thus serving as a suitable reduction.
Could anybody point me in the right direction? Thank you very much.
computability
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
$endgroup$
$begingroup$
Given a sequence of dominoes $p_1,...,p_n$, you can "rotate" the sequence by removing the first piece and appending it to the end of the sequence. With n pieces, you have n sequences each beginning with $p_i$ for $i = 1,...,n$. You then call mPcp once for each of the n sequences. Pcp will be a "Yes" instance iff mPcp is a "Yes" instance for at least one of the n instances.
$endgroup$
– user137481
May 9 '16 at 17:42
$begingroup$
The problem is that calling $mPcp$ for all $i$ could result in an infinite loop if $I$ is a no instance of $Pcp$, thus not satisfying the requirement that the reduction be carried out in a finite number of steps.
$endgroup$
– Dyon J Don Kiwi van Vreumingen
May 10 '16 at 9:12
$begingroup$
Pcp is undecidable. I'm assuming that you are trying to prove that mPcp is undecidable. To start, we assume that mPcp is decidable and let M be the decider for mPcp. A decider always halts. So, there is no "infinite loop" even for 'No" instances. However, if mPcp is decidable, M could also be used to decide Pcp which gives us a contradiction. Hence, mPcp must also be undecidable.
$endgroup$
– user137481
May 10 '16 at 15:16
add a comment |
$begingroup$
Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version requires any matching sequence of "dominoes" $p_{i_1}, p_{i_2}, ..., p_{i_m}$ to start with the first "domino", $p_1$.
I am very well aware of the fact that there exists a match for
an instance $I=langle p_1, ..., p_nrangle$ of $Pcp$ if and only if there exists a match for one of the instances $I_1, I_2, ..., I_n$ of $mPcp$ where $I_j=langle p_j, p_{j+1}, ..., p_n, p_1, ..., p_{j-1}rangle$ for $j=1, ..., n$. In other words, if and only if $I$ is a yes-instance for $Pcp$, there is a way to rotate the list of "dominoes" in a cyclic manner such that the starting piece in the found match for $Pcp$ is put in the first position.
However, it is not clear to me how this observation could lead to a mapping from an instance $I$ of $Pcp$ to the "correct" instance $I_j$ of $mPcp$ that can be carried out in a finite amount of steps for any $I$, thus serving as a suitable reduction.
Could anybody point me in the right direction? Thank you very much.
computability
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
$endgroup$
Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version requires any matching sequence of "dominoes" $p_{i_1}, p_{i_2}, ..., p_{i_m}$ to start with the first "domino", $p_1$.
I am very well aware of the fact that there exists a match for
an instance $I=langle p_1, ..., p_nrangle$ of $Pcp$ if and only if there exists a match for one of the instances $I_1, I_2, ..., I_n$ of $mPcp$ where $I_j=langle p_j, p_{j+1}, ..., p_n, p_1, ..., p_{j-1}rangle$ for $j=1, ..., n$. In other words, if and only if $I$ is a yes-instance for $Pcp$, there is a way to rotate the list of "dominoes" in a cyclic manner such that the starting piece in the found match for $Pcp$ is put in the first position.
However, it is not clear to me how this observation could lead to a mapping from an instance $I$ of $Pcp$ to the "correct" instance $I_j$ of $mPcp$ that can be carried out in a finite amount of steps for any $I$, thus serving as a suitable reduction.
Could anybody point me in the right direction? Thank you very much.
computability
computability
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
edited May 9 '16 at 15:04
Dyon J Don Kiwi van Vreumingen
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
asked May 9 '16 at 10:48
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
1012
1012
$begingroup$
Given a sequence of dominoes $p_1,...,p_n$, you can "rotate" the sequence by removing the first piece and appending it to the end of the sequence. With n pieces, you have n sequences each beginning with $p_i$ for $i = 1,...,n$. You then call mPcp once for each of the n sequences. Pcp will be a "Yes" instance iff mPcp is a "Yes" instance for at least one of the n instances.
$endgroup$
– user137481
May 9 '16 at 17:42
$begingroup$
The problem is that calling $mPcp$ for all $i$ could result in an infinite loop if $I$ is a no instance of $Pcp$, thus not satisfying the requirement that the reduction be carried out in a finite number of steps.
$endgroup$
– Dyon J Don Kiwi van Vreumingen
May 10 '16 at 9:12
$begingroup$
Pcp is undecidable. I'm assuming that you are trying to prove that mPcp is undecidable. To start, we assume that mPcp is decidable and let M be the decider for mPcp. A decider always halts. So, there is no "infinite loop" even for 'No" instances. However, if mPcp is decidable, M could also be used to decide Pcp which gives us a contradiction. Hence, mPcp must also be undecidable.
$endgroup$
– user137481
May 10 '16 at 15:16
add a comment |
$begingroup$
Given a sequence of dominoes $p_1,...,p_n$, you can "rotate" the sequence by removing the first piece and appending it to the end of the sequence. With n pieces, you have n sequences each beginning with $p_i$ for $i = 1,...,n$. You then call mPcp once for each of the n sequences. Pcp will be a "Yes" instance iff mPcp is a "Yes" instance for at least one of the n instances.
$endgroup$
– user137481
May 9 '16 at 17:42
$begingroup$
The problem is that calling $mPcp$ for all $i$ could result in an infinite loop if $I$ is a no instance of $Pcp$, thus not satisfying the requirement that the reduction be carried out in a finite number of steps.
$endgroup$
– Dyon J Don Kiwi van Vreumingen
May 10 '16 at 9:12
$begingroup$
Pcp is undecidable. I'm assuming that you are trying to prove that mPcp is undecidable. To start, we assume that mPcp is decidable and let M be the decider for mPcp. A decider always halts. So, there is no "infinite loop" even for 'No" instances. However, if mPcp is decidable, M could also be used to decide Pcp which gives us a contradiction. Hence, mPcp must also be undecidable.
$endgroup$
– user137481
May 10 '16 at 15:16
$begingroup$
Given a sequence of dominoes $p_1,...,p_n$, you can "rotate" the sequence by removing the first piece and appending it to the end of the sequence. With n pieces, you have n sequences each beginning with $p_i$ for $i = 1,...,n$. You then call mPcp once for each of the n sequences. Pcp will be a "Yes" instance iff mPcp is a "Yes" instance for at least one of the n instances.
$endgroup$
– user137481
May 9 '16 at 17:42
$begingroup$
Given a sequence of dominoes $p_1,...,p_n$, you can "rotate" the sequence by removing the first piece and appending it to the end of the sequence. With n pieces, you have n sequences each beginning with $p_i$ for $i = 1,...,n$. You then call mPcp once for each of the n sequences. Pcp will be a "Yes" instance iff mPcp is a "Yes" instance for at least one of the n instances.
$endgroup$
– user137481
May 9 '16 at 17:42
$begingroup$
The problem is that calling $mPcp$ for all $i$ could result in an infinite loop if $I$ is a no instance of $Pcp$, thus not satisfying the requirement that the reduction be carried out in a finite number of steps.
$endgroup$
– Dyon J Don Kiwi van Vreumingen
May 10 '16 at 9:12
$begingroup$
The problem is that calling $mPcp$ for all $i$ could result in an infinite loop if $I$ is a no instance of $Pcp$, thus not satisfying the requirement that the reduction be carried out in a finite number of steps.
$endgroup$
– Dyon J Don Kiwi van Vreumingen
May 10 '16 at 9:12
$begingroup$
Pcp is undecidable. I'm assuming that you are trying to prove that mPcp is undecidable. To start, we assume that mPcp is decidable and let M be the decider for mPcp. A decider always halts. So, there is no "infinite loop" even for 'No" instances. However, if mPcp is decidable, M could also be used to decide Pcp which gives us a contradiction. Hence, mPcp must also be undecidable.
$endgroup$
– user137481
May 10 '16 at 15:16
$begingroup$
Pcp is undecidable. I'm assuming that you are trying to prove that mPcp is undecidable. To start, we assume that mPcp is decidable and let M be the decider for mPcp. A decider always halts. So, there is no "infinite loop" even for 'No" instances. However, if mPcp is decidable, M could also be used to decide Pcp which gives us a contradiction. Hence, mPcp must also be undecidable.
$endgroup$
– user137481
May 10 '16 at 15:16
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
http://infolab.stanford.edu/~ullman/ialc/slides/slides14.pdf
To summarise what is said in the attached pdf:
Let the dominos be (u1,v1), (u2,v2),...(un,vn).
(* is some symbol not already in the alphabet) For all the u's, put a * after them, and for all the v's, put a star before them, like such:
(u1*,v1), (u2,v2),...(un,*vn)
Now in the MPCP if we wanna start with the first term, we put a * before u1 like such:
(u1,v1), (u2,v2),...(un,*vn)
So now you the first domino MUST start, as it is the only one which has the first symbol matching. If there is a solution to this, it must start with the first domino.
Now to make the endings match, we add a domino:
(@,*@)
where @ is anything not in the alphabet.
Now MPCP is yes iff PCP is yes.
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
$endgroup$
add a comment |
$begingroup$
Put the *s before (or after) each symbol, not the words. So for d=(01101,001) add (0*1*1*0*1*,*0*0*1) but no (01101*,*001). If d is a starting domino add (*0*1*1*0*1*,*0*0*1), too.
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1777944%2freducing-pcp-posts-correspondence-problem-to-mpcp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
http://infolab.stanford.edu/~ullman/ialc/slides/slides14.pdf
To summarise what is said in the attached pdf:
Let the dominos be (u1,v1), (u2,v2),...(un,vn).
(* is some symbol not already in the alphabet) For all the u's, put a * after them, and for all the v's, put a star before them, like such:
(u1*,v1), (u2,v2),...(un,*vn)
Now in the MPCP if we wanna start with the first term, we put a * before u1 like such:
(u1,v1), (u2,v2),...(un,*vn)
So now you the first domino MUST start, as it is the only one which has the first symbol matching. If there is a solution to this, it must start with the first domino.
Now to make the endings match, we add a domino:
(@,*@)
where @ is anything not in the alphabet.
Now MPCP is yes iff PCP is yes.
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
$endgroup$
add a comment |
$begingroup$
http://infolab.stanford.edu/~ullman/ialc/slides/slides14.pdf
To summarise what is said in the attached pdf:
Let the dominos be (u1,v1), (u2,v2),...(un,vn).
(* is some symbol not already in the alphabet) For all the u's, put a * after them, and for all the v's, put a star before them, like such:
(u1*,v1), (u2,v2),...(un,*vn)
Now in the MPCP if we wanna start with the first term, we put a * before u1 like such:
(u1,v1), (u2,v2),...(un,*vn)
So now you the first domino MUST start, as it is the only one which has the first symbol matching. If there is a solution to this, it must start with the first domino.
Now to make the endings match, we add a domino:
(@,*@)
where @ is anything not in the alphabet.
Now MPCP is yes iff PCP is yes.
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
$endgroup$
add a comment |
$begingroup$
http://infolab.stanford.edu/~ullman/ialc/slides/slides14.pdf
To summarise what is said in the attached pdf:
Let the dominos be (u1,v1), (u2,v2),...(un,vn).
(* is some symbol not already in the alphabet) For all the u's, put a * after them, and for all the v's, put a star before them, like such:
(u1*,v1), (u2,v2),...(un,*vn)
Now in the MPCP if we wanna start with the first term, we put a * before u1 like such:
(u1,v1), (u2,v2),...(un,*vn)
So now you the first domino MUST start, as it is the only one which has the first symbol matching. If there is a solution to this, it must start with the first domino.
Now to make the endings match, we add a domino:
(@,*@)
where @ is anything not in the alphabet.
Now MPCP is yes iff PCP is yes.
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
$endgroup$
http://infolab.stanford.edu/~ullman/ialc/slides/slides14.pdf
To summarise what is said in the attached pdf:
Let the dominos be (u1,v1), (u2,v2),...(un,vn).
(* is some symbol not already in the alphabet) For all the u's, put a * after them, and for all the v's, put a star before them, like such:
(u1*,v1), (u2,v2),...(un,*vn)
Now in the MPCP if we wanna start with the first term, we put a * before u1 like such:
(u1,v1), (u2,v2),...(un,*vn)
So now you the first domino MUST start, as it is the only one which has the first symbol matching. If there is a solution to this, it must start with the first domino.
Now to make the endings match, we add a domino:
(@,*@)
where @ is anything not in the alphabet.
Now MPCP is yes iff PCP is yes.
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
edited Nov 21 '16 at 6:20
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
answered Nov 20 '16 at 18:28
PolkaDotPolkaDot
246
246
add a comment |
add a comment |
$begingroup$
Put the *s before (or after) each symbol, not the words. So for d=(01101,001) add (0*1*1*0*1*,*0*0*1) but no (01101*,*001). If d is a starting domino add (*0*1*1*0*1*,*0*0*1), too.
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
$endgroup$
add a comment |
$begingroup$
Put the *s before (or after) each symbol, not the words. So for d=(01101,001) add (0*1*1*0*1*,*0*0*1) but no (01101*,*001). If d is a starting domino add (*0*1*1*0*1*,*0*0*1), too.
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
$endgroup$
add a comment |
$begingroup$
Put the *s before (or after) each symbol, not the words. So for d=(01101,001) add (0*1*1*0*1*,*0*0*1) but no (01101*,*001). If d is a starting domino add (*0*1*1*0*1*,*0*0*1), too.
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
$endgroup$
Put the *s before (or after) each symbol, not the words. So for d=(01101,001) add (0*1*1*0*1*,*0*0*1) but no (01101*,*001). If d is a starting domino add (*0*1*1*0*1*,*0*0*1), too.
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
edited Dec 4 '17 at 15:07
Parcly Taxel
43.1k1372101
43.1k1372101
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
answered Dec 4 '17 at 14:19
tkrisztkrisz
1
1
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1777944%2freducing-pcp-posts-correspondence-problem-to-mpcp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Given a sequence of dominoes $p_1,...,p_n$, you can "rotate" the sequence by removing the first piece and appending it to the end of the sequence. With n pieces, you have n sequences each beginning with $p_i$ for $i = 1,...,n$. You then call mPcp once for each of the n sequences. Pcp will be a "Yes" instance iff mPcp is a "Yes" instance for at least one of the n instances.
$endgroup$
– user137481
May 9 '16 at 17:42
$begingroup$
The problem is that calling $mPcp$ for all $i$ could result in an infinite loop if $I$ is a no instance of $Pcp$, thus not satisfying the requirement that the reduction be carried out in a finite number of steps.
$endgroup$
– Dyon J Don Kiwi van Vreumingen
May 10 '16 at 9:12
$begingroup$
Pcp is undecidable. I'm assuming that you are trying to prove that mPcp is undecidable. To start, we assume that mPcp is decidable and let M be the decider for mPcp. A decider always halts. So, there is no "infinite loop" even for 'No" instances. However, if mPcp is decidable, M could also be used to decide Pcp which gives us a contradiction. Hence, mPcp must also be undecidable.
$endgroup$
– user137481
May 10 '16 at 15:16