Is Chaitin's constant well-defined?
$begingroup$
Chaitin's constant is this amazing example of a real number that we can define, however we can not compute. However, I have a doubt in the claim that the constant is well-defined.
If I understand correctly, however this might very well be the part where I'm wrong, the way Chaitin's constant is defined is by defining a sequence of programs, and then defining the $i$'th binary digit of our number to be $1$ if the $i$'th program halts, and $0$ otherwise. If this sequence enumerates every program, then, because the halting problem is provably undecidable, the constant is uncomputable.
My problem lies in the claim that every program either will halt or not. Take for example the algorithm that enumerates every even natural number greater than $2$ and tries to write it as the sum of two primes, until it finds a number that can not be written this way, at which point it will halt. This program will halt if, and only if, the Goldbach conjecture turns out to be wrong. However, we do not even know if the Goldbach conjecture might be independent of ZFC. If the Goldbach conjecture is independent of ZFC, then is the digit of Chaitin's constant corresponding to this program well-defined?
Even if the Goldbach conjecture turns out to be dependent of ZFC, I doubt that the halting problem is dependent of ZFC for every fixed program.
EDIT: So this apparently depends on the definition of a definable number. A number does not have to be dependent of your universe to be definable. However, then the following follow up question comes to my mind.
If we define a super-definable number to be a number both definable and dependent of ZFC, does there exist a super-definable uncomputable number? Is this known?
EDIT 2: I mean "dependent of ZFC" to say there is a string of symbols in ZFC that determines the value of each digit. But then we can write a program iterating through all strings of symbols until it finds such a string, so the number is computable.
logic definition computability
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
$endgroup$
add a comment |
$begingroup$
Chaitin's constant is this amazing example of a real number that we can define, however we can not compute. However, I have a doubt in the claim that the constant is well-defined.
If I understand correctly, however this might very well be the part where I'm wrong, the way Chaitin's constant is defined is by defining a sequence of programs, and then defining the $i$'th binary digit of our number to be $1$ if the $i$'th program halts, and $0$ otherwise. If this sequence enumerates every program, then, because the halting problem is provably undecidable, the constant is uncomputable.
My problem lies in the claim that every program either will halt or not. Take for example the algorithm that enumerates every even natural number greater than $2$ and tries to write it as the sum of two primes, until it finds a number that can not be written this way, at which point it will halt. This program will halt if, and only if, the Goldbach conjecture turns out to be wrong. However, we do not even know if the Goldbach conjecture might be independent of ZFC. If the Goldbach conjecture is independent of ZFC, then is the digit of Chaitin's constant corresponding to this program well-defined?
Even if the Goldbach conjecture turns out to be dependent of ZFC, I doubt that the halting problem is dependent of ZFC for every fixed program.
EDIT: So this apparently depends on the definition of a definable number. A number does not have to be dependent of your universe to be definable. However, then the following follow up question comes to my mind.
If we define a super-definable number to be a number both definable and dependent of ZFC, does there exist a super-definable uncomputable number? Is this known?
EDIT 2: I mean "dependent of ZFC" to say there is a string of symbols in ZFC that determines the value of each digit. But then we can write a program iterating through all strings of symbols until it finds such a string, so the number is computable.
logic definition computability
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
$endgroup$
2
$begingroup$
Most people, I think, are comfortably Platonist on $Pi_1$ sentences of arithmetic. Either there is a counterexample or there isn’t. If Goldbach is independent of ZFC this simply means it is true but ZFC lacks the requisite power to prove this fact. (And the fact that we’ll probably never know the value of this digit only reinforces the fact that the number is not computable.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:21
$begingroup$
(I say “probably never know” only in the unlikely case that Goldbach turns out independent of ZFC. Perhaps that’s somewhat too strong even still, but as you say, replace Goldbach with something harder.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:44
add a comment |
$begingroup$
Chaitin's constant is this amazing example of a real number that we can define, however we can not compute. However, I have a doubt in the claim that the constant is well-defined.
If I understand correctly, however this might very well be the part where I'm wrong, the way Chaitin's constant is defined is by defining a sequence of programs, and then defining the $i$'th binary digit of our number to be $1$ if the $i$'th program halts, and $0$ otherwise. If this sequence enumerates every program, then, because the halting problem is provably undecidable, the constant is uncomputable.
My problem lies in the claim that every program either will halt or not. Take for example the algorithm that enumerates every even natural number greater than $2$ and tries to write it as the sum of two primes, until it finds a number that can not be written this way, at which point it will halt. This program will halt if, and only if, the Goldbach conjecture turns out to be wrong. However, we do not even know if the Goldbach conjecture might be independent of ZFC. If the Goldbach conjecture is independent of ZFC, then is the digit of Chaitin's constant corresponding to this program well-defined?
Even if the Goldbach conjecture turns out to be dependent of ZFC, I doubt that the halting problem is dependent of ZFC for every fixed program.
EDIT: So this apparently depends on the definition of a definable number. A number does not have to be dependent of your universe to be definable. However, then the following follow up question comes to my mind.
If we define a super-definable number to be a number both definable and dependent of ZFC, does there exist a super-definable uncomputable number? Is this known?
EDIT 2: I mean "dependent of ZFC" to say there is a string of symbols in ZFC that determines the value of each digit. But then we can write a program iterating through all strings of symbols until it finds such a string, so the number is computable.
logic definition computability
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
$endgroup$
Chaitin's constant is this amazing example of a real number that we can define, however we can not compute. However, I have a doubt in the claim that the constant is well-defined.
If I understand correctly, however this might very well be the part where I'm wrong, the way Chaitin's constant is defined is by defining a sequence of programs, and then defining the $i$'th binary digit of our number to be $1$ if the $i$'th program halts, and $0$ otherwise. If this sequence enumerates every program, then, because the halting problem is provably undecidable, the constant is uncomputable.
My problem lies in the claim that every program either will halt or not. Take for example the algorithm that enumerates every even natural number greater than $2$ and tries to write it as the sum of two primes, until it finds a number that can not be written this way, at which point it will halt. This program will halt if, and only if, the Goldbach conjecture turns out to be wrong. However, we do not even know if the Goldbach conjecture might be independent of ZFC. If the Goldbach conjecture is independent of ZFC, then is the digit of Chaitin's constant corresponding to this program well-defined?
Even if the Goldbach conjecture turns out to be dependent of ZFC, I doubt that the halting problem is dependent of ZFC for every fixed program.
EDIT: So this apparently depends on the definition of a definable number. A number does not have to be dependent of your universe to be definable. However, then the following follow up question comes to my mind.
If we define a super-definable number to be a number both definable and dependent of ZFC, does there exist a super-definable uncomputable number? Is this known?
EDIT 2: I mean "dependent of ZFC" to say there is a string of symbols in ZFC that determines the value of each digit. But then we can write a program iterating through all strings of symbols until it finds such a string, so the number is computable.
logic definition computability
logic definition computability
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
edited Dec 18 '18 at 22:18
SmileyCraft
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
asked Dec 18 '18 at 21:34
SmileyCraftSmileyCraft
3,591517
3,591517
2
$begingroup$
Most people, I think, are comfortably Platonist on $Pi_1$ sentences of arithmetic. Either there is a counterexample or there isn’t. If Goldbach is independent of ZFC this simply means it is true but ZFC lacks the requisite power to prove this fact. (And the fact that we’ll probably never know the value of this digit only reinforces the fact that the number is not computable.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:21
$begingroup$
(I say “probably never know” only in the unlikely case that Goldbach turns out independent of ZFC. Perhaps that’s somewhat too strong even still, but as you say, replace Goldbach with something harder.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:44
add a comment |
2
$begingroup$
Most people, I think, are comfortably Platonist on $Pi_1$ sentences of arithmetic. Either there is a counterexample or there isn’t. If Goldbach is independent of ZFC this simply means it is true but ZFC lacks the requisite power to prove this fact. (And the fact that we’ll probably never know the value of this digit only reinforces the fact that the number is not computable.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:21
$begingroup$
(I say “probably never know” only in the unlikely case that Goldbach turns out independent of ZFC. Perhaps that’s somewhat too strong even still, but as you say, replace Goldbach with something harder.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:44
2
2
$begingroup$
Most people, I think, are comfortably Platonist on $Pi_1$ sentences of arithmetic. Either there is a counterexample or there isn’t. If Goldbach is independent of ZFC this simply means it is true but ZFC lacks the requisite power to prove this fact. (And the fact that we’ll probably never know the value of this digit only reinforces the fact that the number is not computable.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:21
$begingroup$
Most people, I think, are comfortably Platonist on $Pi_1$ sentences of arithmetic. Either there is a counterexample or there isn’t. If Goldbach is independent of ZFC this simply means it is true but ZFC lacks the requisite power to prove this fact. (And the fact that we’ll probably never know the value of this digit only reinforces the fact that the number is not computable.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:21
$begingroup$
(I say “probably never know” only in the unlikely case that Goldbach turns out independent of ZFC. Perhaps that’s somewhat too strong even still, but as you say, replace Goldbach with something harder.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:44
$begingroup$
(I say “probably never know” only in the unlikely case that Goldbach turns out independent of ZFC. Perhaps that’s somewhat too strong even still, but as you say, replace Goldbach with something harder.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:44
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Look at the number $xin[0,1]$ whose $n$th digit is $0$ if and only if $2^{aleph_n}=aleph_{n+1}$ and $1$ otherwise. This is certainly a definable real number, I just defined it, but it is consistent to be $0$ and it is consistent to be $1$, and in fact, it is consistent to be any other number whose decimal expansion is only $0$ and $1$. Being definable means you are constant within a fixed universe of your theory. It means it is provably a fixed number. But what is the value? That might depend on your universe.
Or, you know, just take $x=begin{cases}0 &rm CH\ 1 &lnotrm CHend{cases}$ also works.
The key thing to understand is that being definable is Platonistically-constant, but not necessarily constant if you allow for a more multiversial approach (or even a more formalistic approach) to mathematics.
But this is very much like saying that $pi_d$ is half of the length ${xinBbb R^2mid |x|_d=1}$, when $d$ is a metric on $Bbb R^2$. It will invariably depend on the metric you choose.
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
$endgroup$
$begingroup$
Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it.
$endgroup$
– SmileyCraft
Dec 18 '18 at 21:58
1
$begingroup$
Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit?
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 21:59
$begingroup$
Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:02
$begingroup$
What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link.
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 22:04
$begingroup$
That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:14
|
show 1 more comment
$begingroup$
Actually there is no just one Chaitin's constant since the definition depends on the (universal) Turing machine used to define it - see
http://mathworld.wolfram.com/ChaitinsConstant.html
But once the Turing machine is chosen the constant is perfectly well defined. The program testing the Golbach conjecture (running on a given Turing machine) will stop or not, and that will have an impact on the value of the corresponding Chaitin's constant regardless of our ability to determine it. If the Golbach conjecture turns out to be undecidable in ZFC that would imply that it is true because its falsehood would be unveiled by a counterexample and the program would eventually stop. We just would be unable to find out using only the tools of ZFC. That would translate on the impossibility (in ZFC) to determine the value of Chaitin's constant within some degree of accuracy, but it won't change its value.
Edit: After I wrote my answer I noticed that spaceisdarkgreen expressed a very similar idea it the comments. I guess I am a $Pi_1$ platonist :)
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
$endgroup$
$begingroup$
This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:44
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%2f3045735%2fis-chaitins-constant-well-defined%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$
Look at the number $xin[0,1]$ whose $n$th digit is $0$ if and only if $2^{aleph_n}=aleph_{n+1}$ and $1$ otherwise. This is certainly a definable real number, I just defined it, but it is consistent to be $0$ and it is consistent to be $1$, and in fact, it is consistent to be any other number whose decimal expansion is only $0$ and $1$. Being definable means you are constant within a fixed universe of your theory. It means it is provably a fixed number. But what is the value? That might depend on your universe.
Or, you know, just take $x=begin{cases}0 &rm CH\ 1 &lnotrm CHend{cases}$ also works.
The key thing to understand is that being definable is Platonistically-constant, but not necessarily constant if you allow for a more multiversial approach (or even a more formalistic approach) to mathematics.
But this is very much like saying that $pi_d$ is half of the length ${xinBbb R^2mid |x|_d=1}$, when $d$ is a metric on $Bbb R^2$. It will invariably depend on the metric you choose.
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
$endgroup$
$begingroup$
Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it.
$endgroup$
– SmileyCraft
Dec 18 '18 at 21:58
1
$begingroup$
Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit?
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 21:59
$begingroup$
Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:02
$begingroup$
What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link.
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 22:04
$begingroup$
That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:14
|
show 1 more comment
$begingroup$
Look at the number $xin[0,1]$ whose $n$th digit is $0$ if and only if $2^{aleph_n}=aleph_{n+1}$ and $1$ otherwise. This is certainly a definable real number, I just defined it, but it is consistent to be $0$ and it is consistent to be $1$, and in fact, it is consistent to be any other number whose decimal expansion is only $0$ and $1$. Being definable means you are constant within a fixed universe of your theory. It means it is provably a fixed number. But what is the value? That might depend on your universe.
Or, you know, just take $x=begin{cases}0 &rm CH\ 1 &lnotrm CHend{cases}$ also works.
The key thing to understand is that being definable is Platonistically-constant, but not necessarily constant if you allow for a more multiversial approach (or even a more formalistic approach) to mathematics.
But this is very much like saying that $pi_d$ is half of the length ${xinBbb R^2mid |x|_d=1}$, when $d$ is a metric on $Bbb R^2$. It will invariably depend on the metric you choose.
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
$endgroup$
$begingroup$
Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it.
$endgroup$
– SmileyCraft
Dec 18 '18 at 21:58
1
$begingroup$
Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit?
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 21:59
$begingroup$
Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:02
$begingroup$
What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link.
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 22:04
$begingroup$
That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:14
|
show 1 more comment
$begingroup$
Look at the number $xin[0,1]$ whose $n$th digit is $0$ if and only if $2^{aleph_n}=aleph_{n+1}$ and $1$ otherwise. This is certainly a definable real number, I just defined it, but it is consistent to be $0$ and it is consistent to be $1$, and in fact, it is consistent to be any other number whose decimal expansion is only $0$ and $1$. Being definable means you are constant within a fixed universe of your theory. It means it is provably a fixed number. But what is the value? That might depend on your universe.
Or, you know, just take $x=begin{cases}0 &rm CH\ 1 &lnotrm CHend{cases}$ also works.
The key thing to understand is that being definable is Platonistically-constant, but not necessarily constant if you allow for a more multiversial approach (or even a more formalistic approach) to mathematics.
But this is very much like saying that $pi_d$ is half of the length ${xinBbb R^2mid |x|_d=1}$, when $d$ is a metric on $Bbb R^2$. It will invariably depend on the metric you choose.
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
$endgroup$
Look at the number $xin[0,1]$ whose $n$th digit is $0$ if and only if $2^{aleph_n}=aleph_{n+1}$ and $1$ otherwise. This is certainly a definable real number, I just defined it, but it is consistent to be $0$ and it is consistent to be $1$, and in fact, it is consistent to be any other number whose decimal expansion is only $0$ and $1$. Being definable means you are constant within a fixed universe of your theory. It means it is provably a fixed number. But what is the value? That might depend on your universe.
Or, you know, just take $x=begin{cases}0 &rm CH\ 1 &lnotrm CHend{cases}$ also works.
The key thing to understand is that being definable is Platonistically-constant, but not necessarily constant if you allow for a more multiversial approach (or even a more formalistic approach) to mathematics.
But this is very much like saying that $pi_d$ is half of the length ${xinBbb R^2mid |x|_d=1}$, when $d$ is a metric on $Bbb R^2$. It will invariably depend on the metric you choose.
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
answered Dec 18 '18 at 21:46
Asaf Karagila♦Asaf Karagila
304k32433764
304k32433764
$begingroup$
Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it.
$endgroup$
– SmileyCraft
Dec 18 '18 at 21:58
1
$begingroup$
Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit?
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 21:59
$begingroup$
Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:02
$begingroup$
What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link.
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 22:04
$begingroup$
That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:14
|
show 1 more comment
$begingroup$
Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it.
$endgroup$
– SmileyCraft
Dec 18 '18 at 21:58
1
$begingroup$
Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit?
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 21:59
$begingroup$
Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:02
$begingroup$
What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link.
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 22:04
$begingroup$
That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:14
$begingroup$
Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it.
$endgroup$
– SmileyCraft
Dec 18 '18 at 21:58
$begingroup$
Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it.
$endgroup$
– SmileyCraft
Dec 18 '18 at 21:58
1
1
$begingroup$
Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit?
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 21:59
$begingroup$
Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit?
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 21:59
$begingroup$
Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:02
$begingroup$
Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:02
$begingroup$
What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link.
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 22:04
$begingroup$
What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link.
$endgroup$
– Asaf Karagila♦
Dec 18 '18 at 22:04
$begingroup$
That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:14
$begingroup$
That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:14
|
show 1 more comment
$begingroup$
Actually there is no just one Chaitin's constant since the definition depends on the (universal) Turing machine used to define it - see
http://mathworld.wolfram.com/ChaitinsConstant.html
But once the Turing machine is chosen the constant is perfectly well defined. The program testing the Golbach conjecture (running on a given Turing machine) will stop or not, and that will have an impact on the value of the corresponding Chaitin's constant regardless of our ability to determine it. If the Golbach conjecture turns out to be undecidable in ZFC that would imply that it is true because its falsehood would be unveiled by a counterexample and the program would eventually stop. We just would be unable to find out using only the tools of ZFC. That would translate on the impossibility (in ZFC) to determine the value of Chaitin's constant within some degree of accuracy, but it won't change its value.
Edit: After I wrote my answer I noticed that spaceisdarkgreen expressed a very similar idea it the comments. I guess I am a $Pi_1$ platonist :)
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
$endgroup$
$begingroup$
This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:44
add a comment |
$begingroup$
Actually there is no just one Chaitin's constant since the definition depends on the (universal) Turing machine used to define it - see
http://mathworld.wolfram.com/ChaitinsConstant.html
But once the Turing machine is chosen the constant is perfectly well defined. The program testing the Golbach conjecture (running on a given Turing machine) will stop or not, and that will have an impact on the value of the corresponding Chaitin's constant regardless of our ability to determine it. If the Golbach conjecture turns out to be undecidable in ZFC that would imply that it is true because its falsehood would be unveiled by a counterexample and the program would eventually stop. We just would be unable to find out using only the tools of ZFC. That would translate on the impossibility (in ZFC) to determine the value of Chaitin's constant within some degree of accuracy, but it won't change its value.
Edit: After I wrote my answer I noticed that spaceisdarkgreen expressed a very similar idea it the comments. I guess I am a $Pi_1$ platonist :)
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
$endgroup$
$begingroup$
This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:44
add a comment |
$begingroup$
Actually there is no just one Chaitin's constant since the definition depends on the (universal) Turing machine used to define it - see
http://mathworld.wolfram.com/ChaitinsConstant.html
But once the Turing machine is chosen the constant is perfectly well defined. The program testing the Golbach conjecture (running on a given Turing machine) will stop or not, and that will have an impact on the value of the corresponding Chaitin's constant regardless of our ability to determine it. If the Golbach conjecture turns out to be undecidable in ZFC that would imply that it is true because its falsehood would be unveiled by a counterexample and the program would eventually stop. We just would be unable to find out using only the tools of ZFC. That would translate on the impossibility (in ZFC) to determine the value of Chaitin's constant within some degree of accuracy, but it won't change its value.
Edit: After I wrote my answer I noticed that spaceisdarkgreen expressed a very similar idea it the comments. I guess I am a $Pi_1$ platonist :)
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
$endgroup$
Actually there is no just one Chaitin's constant since the definition depends on the (universal) Turing machine used to define it - see
http://mathworld.wolfram.com/ChaitinsConstant.html
But once the Turing machine is chosen the constant is perfectly well defined. The program testing the Golbach conjecture (running on a given Turing machine) will stop or not, and that will have an impact on the value of the corresponding Chaitin's constant regardless of our ability to determine it. If the Golbach conjecture turns out to be undecidable in ZFC that would imply that it is true because its falsehood would be unveiled by a counterexample and the program would eventually stop. We just would be unable to find out using only the tools of ZFC. That would translate on the impossibility (in ZFC) to determine the value of Chaitin's constant within some degree of accuracy, but it won't change its value.
Edit: After I wrote my answer I noticed that spaceisdarkgreen expressed a very similar idea it the comments. I guess I am a $Pi_1$ platonist :)
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
edited Dec 18 '18 at 22:35
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
answered Dec 18 '18 at 22:29
mlerma54mlerma54
1,177148
1,177148
$begingroup$
This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:44
add a comment |
$begingroup$
This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:44
$begingroup$
This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:44
$begingroup$
This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt.
$endgroup$
– SmileyCraft
Dec 18 '18 at 22:44
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%2f3045735%2fis-chaitins-constant-well-defined%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
2
$begingroup$
Most people, I think, are comfortably Platonist on $Pi_1$ sentences of arithmetic. Either there is a counterexample or there isn’t. If Goldbach is independent of ZFC this simply means it is true but ZFC lacks the requisite power to prove this fact. (And the fact that we’ll probably never know the value of this digit only reinforces the fact that the number is not computable.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:21
$begingroup$
(I say “probably never know” only in the unlikely case that Goldbach turns out independent of ZFC. Perhaps that’s somewhat too strong even still, but as you say, replace Goldbach with something harder.)
$endgroup$
– spaceisdarkgreen
Dec 18 '18 at 22:44