An example of an easy to understand undecidable problem Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Do complex numbers really exist?Why is Peano arithmetic undecidable?Using halting problem to prove undecidable problemsUndecidable existence theoremsUse of undecidabilityDoes there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?An example for a calculation where imaginary numbers are used but don't occur in the question or the solution.How to come up with a counter example in linear algebraWhat's the difference between “unprovable” and “undecidable”?Does Temporal Logic have undecidable propositions?Nonalgorithmic and approximate solutions to undecidable problems / formulas?
I'm thinking of a number
How to rotate it perfectly?
Limit for e and 1/e
Windows 10: How to Lock (not sleep) laptop on lid close?
Estimated State payment too big --> money back; + 2018 Tax Reform
What do you call a plan that's an alternative plan in case your initial plan fails?
How to colour the US map with Yellow, Green, Red and Blue to minimize the number of states with the colour of Green
How are presidential pardons supposed to be used?
Can smartphones with the same camera sensor have different image quality?
Active filter with series inductor and resistor - do these exist?
How to market an anarchic city as a tourism spot to people living in civilized areas?
Was credit for the black hole image misattributed?
Do we know why communications with Beresheet and NASA were lost during the attempted landing of the Moon lander?
Passing functions in C++
Who can trigger ship-wide alerts in Star Trek?
Autumning in love
Why don't the Weasley twins use magic outside of school if the Trace can only find the location of spells cast?
Using "nakedly" instead of "with nothing on"
What is the electric potential inside a point charge?
Need a suitable toxic chemical for a murder plot in my novel
Determine whether f is a function, an injection, a surjection
Strange behaviour of Check
What kind of display is this?
Is it possible to ask for a hotel room without minibar/extra services?
An example of an easy to understand undecidable problem
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Do complex numbers really exist?Why is Peano arithmetic undecidable?Using halting problem to prove undecidable problemsUndecidable existence theoremsUse of undecidabilityDoes there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?An example for a calculation where imaginary numbers are used but don't occur in the question or the solution.How to come up with a counter example in linear algebraWhat's the difference between “unprovable” and “undecidable”?Does Temporal Logic have undecidable propositions?Nonalgorithmic and approximate solutions to undecidable problems / formulas?
$begingroup$
I am looking for an undecidable problem that I could give as an easy example in a presentation to the general public. I mean easy in the sense that the mathematics behind it can be described, well, without mathematics, that is with analogies and intuition, avoiding technicalities.
logic examples-counterexamples
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
$endgroup$
add a comment |
$begingroup$
I am looking for an undecidable problem that I could give as an easy example in a presentation to the general public. I mean easy in the sense that the mathematics behind it can be described, well, without mathematics, that is with analogies and intuition, avoiding technicalities.
logic examples-counterexamples
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
$endgroup$
$begingroup$
The formula $forall x, y quad xy=xy$ is undecidable in the theory describing the usual group theory.
$endgroup$
– Watson
Aug 29 '16 at 18:08
add a comment |
$begingroup$
I am looking for an undecidable problem that I could give as an easy example in a presentation to the general public. I mean easy in the sense that the mathematics behind it can be described, well, without mathematics, that is with analogies and intuition, avoiding technicalities.
logic examples-counterexamples
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
$endgroup$
I am looking for an undecidable problem that I could give as an easy example in a presentation to the general public. I mean easy in the sense that the mathematics behind it can be described, well, without mathematics, that is with analogies and intuition, avoiding technicalities.
logic examples-counterexamples
logic examples-counterexamples
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
edited Nov 10 '11 at 7:15
Asaf Karagila♦
308k33441775
308k33441775
asked Nov 10 '11 at 4:35
user19220
$begingroup$
The formula $forall x, y quad xy=xy$ is undecidable in the theory describing the usual group theory.
$endgroup$
– Watson
Aug 29 '16 at 18:08
add a comment |
$begingroup$
The formula $forall x, y quad xy=xy$ is undecidable in the theory describing the usual group theory.
$endgroup$
– Watson
Aug 29 '16 at 18:08
$begingroup$
The formula $forall x, y quad xy=xy$ is undecidable in the theory describing the usual group theory.
$endgroup$
– Watson
Aug 29 '16 at 18:08
$begingroup$
The formula $forall x, y quad xy=xy$ is undecidable in the theory describing the usual group theory.
$endgroup$
– Watson
Aug 29 '16 at 18:08
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
"Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?"
(See also word problem)
"Does this statement follow from these axioms?"
(Hilbert's Entscheidungsproblem)
"Does this computer program ever stop?"
"Does this computer program have any security vulnerabilities?"
"Does this computer program do <any non-trivial statement>?"
(The halting-problem, from which all semantic properties can be reduced)
"Can this set of domino-like tiles tile the plane?"
(See Tiling Problem)
"Does this Diophantine equation have an integer solution?"
(See Hilbert's Tenth Problem)
"Given two lists of strings, is there a list of indices such that the concatenations from both lists are equal?"
(See Post correspondence problem)
There is also a large list on wikipedia.
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
$endgroup$
$begingroup$
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad.
$endgroup$
– Daniel
Nov 19 '13 at 3:23
$begingroup$
Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
$endgroup$
– Hurkyl
Mar 26 at 4:31
add a comment |
$begingroup$
I think the Post correspondence problem is a very good example of a simple undecideable problem that is also relatively unknown.
Given a finite set of string tuples
(a , bba) X
(ab, aa) Y
(bba, bb) Z
the problem is to determine if there is a finite sequence of these tuples , allowing for repetition, such that the concatenation of the first half is equal to the concatenation of second half
(bba, bb) Z
(ab, aa) Y
(bba, bb) Z
(a, bba) X
------------ gives
(bbaabbbaa, bbaabbbaa)
The only big issue I have with this problem is that the only undecideability proof I know of falls back on simulating a Turing machine - it would be nice to find a more elementary alternate version.
answered Nov 10 '11 at 13:01
hugomghugomg
24115
$endgroup$
$begingroup$
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character
$endgroup$
– miracle173
Jan 3 '12 at 1:33
$begingroup$
@miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments<!-- -->to bypass the edit size limit if you need to fix typos in the future)
$endgroup$
– hugomg
Jan 3 '12 at 2:25
$begingroup$
The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg.
$endgroup$
– user1729
Apr 5 at 12:20
add a comment |
$begingroup$
May be you want to check these:
Alan_Turing_and_Undecidable_Problems_in_Mathematics on fora.tv
what-are-the-most-attractive-turing-undecidable-problems-in-mathematics on mathoverflow
MagicSquare on mathworld.wolfram
edited Apr 13 '17 at 12:58
Community♦
1
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
$endgroup$
$begingroup$
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be.
$endgroup$
– ShreevatsaR
Nov 10 '11 at 8:20
$begingroup$
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead?
$endgroup$
– NoChance
Nov 10 '11 at 10:12
$begingroup$
Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
$endgroup$
– Did
Nov 10 '11 at 10:20
$begingroup$
@DidierPiau: Thank you for your comment and clear instructions.
$endgroup$
– NoChance
Nov 10 '11 at 13:06
add a comment |
$begingroup$
"does this computer program ever stop?"
"does this equation have any solutions?" (of course you mean polynomial equation with integer solutions, but for a general public presentation you can probably get away with just "equation" and "solutions").
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
$endgroup$
add a comment |
$begingroup$
Maybe consider some Wang Tiles.
answered Nov 10 '11 at 5:50
tomtom
1,71411733
$endgroup$
add a comment |
Your Answer
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%2f80745%2fan-example-of-an-easy-to-understand-undecidable-problem%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
"Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?"
(See also word problem)
"Does this statement follow from these axioms?"
(Hilbert's Entscheidungsproblem)
"Does this computer program ever stop?"
"Does this computer program have any security vulnerabilities?"
"Does this computer program do <any non-trivial statement>?"
(The halting-problem, from which all semantic properties can be reduced)
"Can this set of domino-like tiles tile the plane?"
(See Tiling Problem)
"Does this Diophantine equation have an integer solution?"
(See Hilbert's Tenth Problem)
"Given two lists of strings, is there a list of indices such that the concatenations from both lists are equal?"
(See Post correspondence problem)
There is also a large list on wikipedia.
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
$endgroup$
$begingroup$
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad.
$endgroup$
– Daniel
Nov 19 '13 at 3:23
$begingroup$
Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
$endgroup$
– Hurkyl
Mar 26 at 4:31
add a comment |
$begingroup$
"Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?"
(See also word problem)
"Does this statement follow from these axioms?"
(Hilbert's Entscheidungsproblem)
"Does this computer program ever stop?"
"Does this computer program have any security vulnerabilities?"
"Does this computer program do <any non-trivial statement>?"
(The halting-problem, from which all semantic properties can be reduced)
"Can this set of domino-like tiles tile the plane?"
(See Tiling Problem)
"Does this Diophantine equation have an integer solution?"
(See Hilbert's Tenth Problem)
"Given two lists of strings, is there a list of indices such that the concatenations from both lists are equal?"
(See Post correspondence problem)
There is also a large list on wikipedia.
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
$endgroup$
$begingroup$
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad.
$endgroup$
– Daniel
Nov 19 '13 at 3:23
$begingroup$
Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
$endgroup$
– Hurkyl
Mar 26 at 4:31
add a comment |
$begingroup$
"Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?"
(See also word problem)
"Does this statement follow from these axioms?"
(Hilbert's Entscheidungsproblem)
"Does this computer program ever stop?"
"Does this computer program have any security vulnerabilities?"
"Does this computer program do <any non-trivial statement>?"
(The halting-problem, from which all semantic properties can be reduced)
"Can this set of domino-like tiles tile the plane?"
(See Tiling Problem)
"Does this Diophantine equation have an integer solution?"
(See Hilbert's Tenth Problem)
"Given two lists of strings, is there a list of indices such that the concatenations from both lists are equal?"
(See Post correspondence problem)
There is also a large list on wikipedia.
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
$endgroup$
"Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?"
(See also word problem)
"Does this statement follow from these axioms?"
(Hilbert's Entscheidungsproblem)
"Does this computer program ever stop?"
"Does this computer program have any security vulnerabilities?"
"Does this computer program do <any non-trivial statement>?"
(The halting-problem, from which all semantic properties can be reduced)
"Can this set of domino-like tiles tile the plane?"
(See Tiling Problem)
"Does this Diophantine equation have an integer solution?"
(See Hilbert's Tenth Problem)
"Given two lists of strings, is there a list of indices such that the concatenations from both lists are equal?"
(See Post correspondence problem)
There is also a large list on wikipedia.
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
edited Mar 25 at 17:39
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
answered Nov 10 '11 at 6:39
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
5,88342943
5,88342943
$begingroup$
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad.
$endgroup$
– Daniel
Nov 19 '13 at 3:23
$begingroup$
Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
$endgroup$
– Hurkyl
Mar 26 at 4:31
add a comment |
$begingroup$
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad.
$endgroup$
– Daniel
Nov 19 '13 at 3:23
$begingroup$
Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
$endgroup$
– Hurkyl
Mar 26 at 4:31
$begingroup$
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad.
$endgroup$
– Daniel
Nov 19 '13 at 3:23
$begingroup$
Wikipedia's explanation of the proof of undecidability for the halting problem is really bad.
$endgroup$
– Daniel
Nov 19 '13 at 3:23
$begingroup$
Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
$endgroup$
– Hurkyl
Mar 26 at 4:31
$begingroup$
Regarding the first example, it's important to consider how you're specifying real numbers. For example, the first-order arithmetic of real numbers is complete; one can always decide, and do so algorithmically, whether two real numbers are equal when they're sepcified in the language of first-order real arithmetic. (also called real-closed fields)
$endgroup$
– Hurkyl
Mar 26 at 4:31
add a comment |
$begingroup$
I think the Post correspondence problem is a very good example of a simple undecideable problem that is also relatively unknown.
Given a finite set of string tuples
(a , bba) X
(ab, aa) Y
(bba, bb) Z
the problem is to determine if there is a finite sequence of these tuples , allowing for repetition, such that the concatenation of the first half is equal to the concatenation of second half
(bba, bb) Z
(ab, aa) Y
(bba, bb) Z
(a, bba) X
------------ gives
(bbaabbbaa, bbaabbbaa)
The only big issue I have with this problem is that the only undecideability proof I know of falls back on simulating a Turing machine - it would be nice to find a more elementary alternate version.
answered Nov 10 '11 at 13:01
hugomghugomg
24115
$endgroup$
$begingroup$
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character
$endgroup$
– miracle173
Jan 3 '12 at 1:33
$begingroup$
@miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments<!-- -->to bypass the edit size limit if you need to fix typos in the future)
$endgroup$
– hugomg
Jan 3 '12 at 2:25
$begingroup$
The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg.
$endgroup$
– user1729
Apr 5 at 12:20
add a comment |
$begingroup$
I think the Post correspondence problem is a very good example of a simple undecideable problem that is also relatively unknown.
Given a finite set of string tuples
(a , bba) X
(ab, aa) Y
(bba, bb) Z
the problem is to determine if there is a finite sequence of these tuples , allowing for repetition, such that the concatenation of the first half is equal to the concatenation of second half
(bba, bb) Z
(ab, aa) Y
(bba, bb) Z
(a, bba) X
------------ gives
(bbaabbbaa, bbaabbbaa)
The only big issue I have with this problem is that the only undecideability proof I know of falls back on simulating a Turing machine - it would be nice to find a more elementary alternate version.
answered Nov 10 '11 at 13:01
hugomghugomg
24115
$endgroup$
$begingroup$
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character
$endgroup$
– miracle173
Jan 3 '12 at 1:33
$begingroup$
@miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments<!-- -->to bypass the edit size limit if you need to fix typos in the future)
$endgroup$
– hugomg
Jan 3 '12 at 2:25
$begingroup$
The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg.
$endgroup$
– user1729
Apr 5 at 12:20
add a comment |
$begingroup$
I think the Post correspondence problem is a very good example of a simple undecideable problem that is also relatively unknown.
Given a finite set of string tuples
(a , bba) X
(ab, aa) Y
(bba, bb) Z
the problem is to determine if there is a finite sequence of these tuples , allowing for repetition, such that the concatenation of the first half is equal to the concatenation of second half
(bba, bb) Z
(ab, aa) Y
(bba, bb) Z
(a, bba) X
------------ gives
(bbaabbbaa, bbaabbbaa)
The only big issue I have with this problem is that the only undecideability proof I know of falls back on simulating a Turing machine - it would be nice to find a more elementary alternate version.
answered Nov 10 '11 at 13:01
hugomghugomg
24115
$endgroup$
I think the Post correspondence problem is a very good example of a simple undecideable problem that is also relatively unknown.
Given a finite set of string tuples
(a , bba) X
(ab, aa) Y
(bba, bb) Z
the problem is to determine if there is a finite sequence of these tuples , allowing for repetition, such that the concatenation of the first half is equal to the concatenation of second half
(bba, bb) Z
(ab, aa) Y
(bba, bb) Z
(a, bba) X
------------ gives
(bbaabbbaa, bbaabbbaa)
The only big issue I have with this problem is that the only undecideability proof I know of falls back on simulating a Turing machine - it would be nice to find a more elementary alternate version.
answered Nov 10 '11 at 13:01
hugomghugomg
24115
edited Mar 14 '15 at 1:23
answered Nov 10 '11 at 13:01
hugomghugomg
24115
answered Nov 10 '11 at 13:01
hugomghugomg
24115
answered Nov 10 '11 at 13:01
hugomghugomg
24115
24115
$begingroup$
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character
$endgroup$
– miracle173
Jan 3 '12 at 1:33
$begingroup$
@miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments<!-- -->to bypass the edit size limit if you need to fix typos in the future)
$endgroup$
– hugomg
Jan 3 '12 at 2:25
$begingroup$
The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg.
$endgroup$
– user1729
Apr 5 at 12:20
add a comment |
$begingroup$
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character
$endgroup$
– miracle173
Jan 3 '12 at 1:33
$begingroup$
@miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments<!-- -->to bypass the edit size limit if you need to fix typos in the future)
$endgroup$
– hugomg
Jan 3 '12 at 2:25
$begingroup$
The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg.
$endgroup$
– user1729
Apr 5 at 12:20
$begingroup$
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character
$endgroup$
– miracle173
Jan 3 '12 at 1:33
$begingroup$
there is a typo (a,bba) instead of (a,baa) for tuple 1. but it is not allowed to change only one character
$endgroup$
– miracle173
Jan 3 '12 at 1:33
$begingroup$
@miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments
<!-- --> to bypass the edit size limit if you need to fix typos in the future)$endgroup$
– hugomg
Jan 3 '12 at 2:25
$begingroup$
@miracle173. Thanks! (btw, if I remember correctly you can add invisible html comments
<!-- --> to bypass the edit size limit if you need to fix typos in the future)$endgroup$
– hugomg
Jan 3 '12 at 2:25
$begingroup$
The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg.
$endgroup$
– user1729
Apr 5 at 12:20
$begingroup$
The PCP can be reduced to the word problem for semigroups (and, more generally, for rewriting systems). This gives a more elementary proof of undecidability, if you are willing to accept that the word problem for semigroups/rewriting systems is undecidable! See Harju T., Karhumäki J. (1997) Morphisms. In: Rozenberg G., Salomaa A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg.
$endgroup$
– user1729
Apr 5 at 12:20
add a comment |
$begingroup$
May be you want to check these:
Alan_Turing_and_Undecidable_Problems_in_Mathematics on fora.tv
what-are-the-most-attractive-turing-undecidable-problems-in-mathematics on mathoverflow
MagicSquare on mathworld.wolfram
edited Apr 13 '17 at 12:58
Community♦
1
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
$endgroup$
$begingroup$
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be.
$endgroup$
– ShreevatsaR
Nov 10 '11 at 8:20
$begingroup$
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead?
$endgroup$
– NoChance
Nov 10 '11 at 10:12
$begingroup$
Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
$endgroup$
– Did
Nov 10 '11 at 10:20
$begingroup$
@DidierPiau: Thank you for your comment and clear instructions.
$endgroup$
– NoChance
Nov 10 '11 at 13:06
add a comment |
$begingroup$
May be you want to check these:
Alan_Turing_and_Undecidable_Problems_in_Mathematics on fora.tv
what-are-the-most-attractive-turing-undecidable-problems-in-mathematics on mathoverflow
MagicSquare on mathworld.wolfram
edited Apr 13 '17 at 12:58
Community♦
1
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
$endgroup$
$begingroup$
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be.
$endgroup$
– ShreevatsaR
Nov 10 '11 at 8:20
$begingroup$
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead?
$endgroup$
– NoChance
Nov 10 '11 at 10:12
$begingroup$
Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
$endgroup$
– Did
Nov 10 '11 at 10:20
$begingroup$
@DidierPiau: Thank you for your comment and clear instructions.
$endgroup$
– NoChance
Nov 10 '11 at 13:06
add a comment |
$begingroup$
May be you want to check these:
Alan_Turing_and_Undecidable_Problems_in_Mathematics on fora.tv
what-are-the-most-attractive-turing-undecidable-problems-in-mathematics on mathoverflow
MagicSquare on mathworld.wolfram
edited Apr 13 '17 at 12:58
Community♦
1
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
$endgroup$
May be you want to check these:
Alan_Turing_and_Undecidable_Problems_in_Mathematics on fora.tv
what-are-the-most-attractive-turing-undecidable-problems-in-mathematics on mathoverflow
MagicSquare on mathworld.wolfram
edited Apr 13 '17 at 12:58
Community♦
1
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
edited Apr 13 '17 at 12:58
Community♦
1
edited Apr 13 '17 at 12:58
Community♦
1
edited Apr 13 '17 at 12:58
Community♦
1
1
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
answered Nov 10 '11 at 4:51
NoChanceNoChance
3,76621321
3,76621321
$begingroup$
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be.
$endgroup$
– ShreevatsaR
Nov 10 '11 at 8:20
$begingroup$
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead?
$endgroup$
– NoChance
Nov 10 '11 at 10:12
$begingroup$
Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
$endgroup$
– Did
Nov 10 '11 at 10:20
$begingroup$
@DidierPiau: Thank you for your comment and clear instructions.
$endgroup$
– NoChance
Nov 10 '11 at 13:06
add a comment |
$begingroup$
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be.
$endgroup$
– ShreevatsaR
Nov 10 '11 at 8:20
$begingroup$
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead?
$endgroup$
– NoChance
Nov 10 '11 at 10:12
$begingroup$
Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
$endgroup$
– Did
Nov 10 '11 at 10:20
$begingroup$
@DidierPiau: Thank you for your comment and clear instructions.
$endgroup$
– NoChance
Nov 10 '11 at 13:06
$begingroup$
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be.
$endgroup$
– ShreevatsaR
Nov 10 '11 at 8:20
$begingroup$
Link rot happens. Imagine someone cannot click on any links, and consider how useful your answer will be.
$endgroup$
– ShreevatsaR
Nov 10 '11 at 8:20
$begingroup$
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead?
$endgroup$
– NoChance
Nov 10 '11 at 10:12
$begingroup$
@ShreevatsaR: Thanks for you suggestion. Do you prefer placing the text of the url instead?
$endgroup$
– NoChance
Nov 10 '11 at 10:12
$begingroup$
Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
$endgroup$
– Did
Nov 10 '11 at 10:20
$begingroup$
Please do not post answers which force people to click on the links to know what they contain. See the simple way I used to avoid this by consulting the modified source of your post.
$endgroup$
– Did
Nov 10 '11 at 10:20
$begingroup$
@DidierPiau: Thank you for your comment and clear instructions.
$endgroup$
– NoChance
Nov 10 '11 at 13:06
$begingroup$
@DidierPiau: Thank you for your comment and clear instructions.
$endgroup$
– NoChance
Nov 10 '11 at 13:06
add a comment |
$begingroup$
"does this computer program ever stop?"
"does this equation have any solutions?" (of course you mean polynomial equation with integer solutions, but for a general public presentation you can probably get away with just "equation" and "solutions").
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
$endgroup$
add a comment |
$begingroup$
"does this computer program ever stop?"
"does this equation have any solutions?" (of course you mean polynomial equation with integer solutions, but for a general public presentation you can probably get away with just "equation" and "solutions").
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
$endgroup$
add a comment |
$begingroup$
"does this computer program ever stop?"
"does this equation have any solutions?" (of course you mean polynomial equation with integer solutions, but for a general public presentation you can probably get away with just "equation" and "solutions").
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
$endgroup$
"does this computer program ever stop?"
"does this equation have any solutions?" (of course you mean polynomial equation with integer solutions, but for a general public presentation you can probably get away with just "equation" and "solutions").
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
answered Nov 10 '11 at 4:44
Alon AmitAlon Amit
10.7k3768
10.7k3768
add a comment |
add a comment |
$begingroup$
Maybe consider some Wang Tiles.
answered Nov 10 '11 at 5:50
tomtom
1,71411733
$endgroup$
add a comment |
$begingroup$
Maybe consider some Wang Tiles.
answered Nov 10 '11 at 5:50
tomtom
1,71411733
$endgroup$
add a comment |
$begingroup$
Maybe consider some Wang Tiles.
answered Nov 10 '11 at 5:50
tomtom
1,71411733
$endgroup$
Maybe consider some Wang Tiles.
answered Nov 10 '11 at 5:50
tomtom
1,71411733
answered Nov 10 '11 at 5:50
tomtom
1,71411733
answered Nov 10 '11 at 5:50
tomtom
1,71411733
answered Nov 10 '11 at 5:50
tomtom
1,71411733
1,71411733
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%2f80745%2fan-example-of-an-easy-to-understand-undecidable-problem%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$
The formula $forall x, y quad xy=xy$ is undecidable in the theory describing the usual group theory.
$endgroup$
– Watson
Aug 29 '16 at 18:08