Mixing
Well-definedness of uncomputable functions.
$begingroup$
I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never had any doubt that things such as the busy beaver function were well-defined. Then I read this article where it was stated that two numbers described by uncomputable functions like BB might be incomparable within a certain system of axioms - it could be independent of the system which one was larger. This was taken to mean that one might not be larger than the other at all. I took this to suggest that even a simple uncomputable function like BB(n) could be undefined in a sense.
However, it seems to me that, given two numbers, it should always be possible to decide which is bigger. It also seems like the busy beaver function should be well-defined since it is making a precise statement about machines which could theoretically be implemented in the physical world.
So, are uncomputable functions well-defined in general? What characteristics would make one well-defined or not, and is there something I'm conceptually missing in the way that I am approaching these questions? Thank you for helping me understand!
set-theory computability foundations
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
$endgroup$
add a comment |
$begingroup$
I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never had any doubt that things such as the busy beaver function were well-defined. Then I read this article where it was stated that two numbers described by uncomputable functions like BB might be incomparable within a certain system of axioms - it could be independent of the system which one was larger. This was taken to mean that one might not be larger than the other at all. I took this to suggest that even a simple uncomputable function like BB(n) could be undefined in a sense.
However, it seems to me that, given two numbers, it should always be possible to decide which is bigger. It also seems like the busy beaver function should be well-defined since it is making a precise statement about machines which could theoretically be implemented in the physical world.
So, are uncomputable functions well-defined in general? What characteristics would make one well-defined or not, and is there something I'm conceptually missing in the way that I am approaching these questions? Thank you for helping me understand!
set-theory computability foundations
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
$endgroup$
2
$begingroup$
Assuming you are not an ultra-finitist, the busy beaver function is definitely well-defined mathematically. Well-definedness as an integer-valued function is not the same as being uncomputable
$endgroup$
– Brevan Ellefsen
Jan 17 at 4:30
$begingroup$
You are able to always tell which number I should bigger, assuming a universe with nigh infinite data storage and assuming you have a lot of spare time (and I mean a lot)...
$endgroup$
– L. McDonald
Jan 19 at 9:25
$begingroup$
@L.McDonald This depends on what you mean by 'given two numbers'. If the meaning is 'given two properties that each provably define a unique number', then it is not necessarily effectively decidable which number is bigger.
$endgroup$
– spaceisdarkgreen
Jan 19 at 19:20
add a comment |
$begingroup$
I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never had any doubt that things such as the busy beaver function were well-defined. Then I read this article where it was stated that two numbers described by uncomputable functions like BB might be incomparable within a certain system of axioms - it could be independent of the system which one was larger. This was taken to mean that one might not be larger than the other at all. I took this to suggest that even a simple uncomputable function like BB(n) could be undefined in a sense.
However, it seems to me that, given two numbers, it should always be possible to decide which is bigger. It also seems like the busy beaver function should be well-defined since it is making a precise statement about machines which could theoretically be implemented in the physical world.
So, are uncomputable functions well-defined in general? What characteristics would make one well-defined or not, and is there something I'm conceptually missing in the way that I am approaching these questions? Thank you for helping me understand!
set-theory computability foundations
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
$endgroup$
I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never had any doubt that things such as the busy beaver function were well-defined. Then I read this article where it was stated that two numbers described by uncomputable functions like BB might be incomparable within a certain system of axioms - it could be independent of the system which one was larger. This was taken to mean that one might not be larger than the other at all. I took this to suggest that even a simple uncomputable function like BB(n) could be undefined in a sense.
However, it seems to me that, given two numbers, it should always be possible to decide which is bigger. It also seems like the busy beaver function should be well-defined since it is making a precise statement about machines which could theoretically be implemented in the physical world.
So, are uncomputable functions well-defined in general? What characteristics would make one well-defined or not, and is there something I'm conceptually missing in the way that I am approaching these questions? Thank you for helping me understand!
set-theory computability foundations
set-theory computability foundations
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
edited Jan 17 at 13:59
CyborgOctopus
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
asked Jan 17 at 4:00
CyborgOctopusCyborgOctopus
856
856
2
$begingroup$
Assuming you are not an ultra-finitist, the busy beaver function is definitely well-defined mathematically. Well-definedness as an integer-valued function is not the same as being uncomputable
$endgroup$
– Brevan Ellefsen
Jan 17 at 4:30
$begingroup$
You are able to always tell which number I should bigger, assuming a universe with nigh infinite data storage and assuming you have a lot of spare time (and I mean a lot)...
$endgroup$
– L. McDonald
Jan 19 at 9:25
$begingroup$
@L.McDonald This depends on what you mean by 'given two numbers'. If the meaning is 'given two properties that each provably define a unique number', then it is not necessarily effectively decidable which number is bigger.
$endgroup$
– spaceisdarkgreen
Jan 19 at 19:20
add a comment |
2
$begingroup$
Assuming you are not an ultra-finitist, the busy beaver function is definitely well-defined mathematically. Well-definedness as an integer-valued function is not the same as being uncomputable
$endgroup$
– Brevan Ellefsen
Jan 17 at 4:30
$begingroup$
You are able to always tell which number I should bigger, assuming a universe with nigh infinite data storage and assuming you have a lot of spare time (and I mean a lot)...
$endgroup$
– L. McDonald
Jan 19 at 9:25
$begingroup$
@L.McDonald This depends on what you mean by 'given two numbers'. If the meaning is 'given two properties that each provably define a unique number', then it is not necessarily effectively decidable which number is bigger.
$endgroup$
– spaceisdarkgreen
Jan 19 at 19:20
2
2
$begingroup$
Assuming you are not an ultra-finitist, the busy beaver function is definitely well-defined mathematically. Well-definedness as an integer-valued function is not the same as being uncomputable
$endgroup$
– Brevan Ellefsen
Jan 17 at 4:30
$begingroup$
Assuming you are not an ultra-finitist, the busy beaver function is definitely well-defined mathematically. Well-definedness as an integer-valued function is not the same as being uncomputable
$endgroup$
– Brevan Ellefsen
Jan 17 at 4:30
$begingroup$
You are able to always tell which number I should bigger, assuming a universe with nigh infinite data storage and assuming you have a lot of spare time (and I mean a lot)...
$endgroup$
– L. McDonald
Jan 19 at 9:25
$begingroup$
You are able to always tell which number I should bigger, assuming a universe with nigh infinite data storage and assuming you have a lot of spare time (and I mean a lot)...
$endgroup$
– L. McDonald
Jan 19 at 9:25
$begingroup$
@L.McDonald This depends on what you mean by 'given two numbers'. If the meaning is 'given two properties that each provably define a unique number', then it is not necessarily effectively decidable which number is bigger.
$endgroup$
– spaceisdarkgreen
Jan 19 at 19:20
$begingroup$
@L.McDonald This depends on what you mean by 'given two numbers'. If the meaning is 'given two properties that each provably define a unique number', then it is not necessarily effectively decidable which number is bigger.
$endgroup$
– spaceisdarkgreen
Jan 19 at 19:20
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The busy-beaver-function is well-defined because every halting turing machine can only write a finite number of ones on the tape, hence there must be a champion, and $bb(n)$ is the number of ones this champion writes down.
But the busy-beaver-function is not computable because we cannot determine which turing machines halt and which do not. This (and only this) prevents us from determining the busy-beaver-champion and therefore determining $bb(n)$ in general.
"Computable" means that there is an algorithm being able for every n to either determine $f(n)$ or determine that $f(n)$ is not defined.
"Well-defined" means that there is a description guaranteeing that for every $n$ there is either only one possible value $f(n)$ or that the function is not defined. (It is not necessary that this $f(n)$ can actually be determined , if $f(n)$ is defined.)
answered Jan 19 at 13:54
PeterPeter
48k1139133
$endgroup$
$begingroup$
"Computable" means that there is an algorithm being able to determine f(n) for every n. Not really, partial functions are allowed.
$endgroup$
– Wuestenfux
Jan 20 at 12:20
1
$begingroup$
@Peter I think using computable for a program halting on all inputs is fine. I think it is quite commonly used. For example, the following are equivalent: (a1) computable (a2) recursive (a3) total computable (a4) total recursive. Similarly, the following are also equivalent: (b1) partial computable (b2) partial recursive. Though there are probably some sources that use "computable" to mean "partial computable" and, quite honestly, I think that kind of usage is very confusing (and I very rarely complain about terminology). There are only a couple of exceptions to it (mentioned in next comment).
$endgroup$
– SSequence
Jan 26 at 20:04
1
$begingroup$
Sometimes when people say "collection of computable functions", it can mean "collection of partial computable functions". Otherwise I think the normal association of "computable" with "total computable" is fine. Of course it can be a bit context dependent occasionally so using "total computable" for emphasis can be useful at times. Also, "algorithm" is generally associated with a function halting on all inputs. One thing though, the general convention for a partial computable function is to take it as "undefined" only on those input values for which it does not halt. (cont.)
$endgroup$
– SSequence
Jan 26 at 20:08
1
$begingroup$
So "normally", when a total comptuable function (also called algorithm normally.... unless the context makes it clear that something else is meant) computes a function, the function is presumed to be defined for all values in its domain. Finally note that "partial computable functions" are, by convention, meant to include all functions that may or may not halt on all the inputs. In other words, the collection of partial computable functions contains collection of total compuable functions as strict subset.
$endgroup$
– SSequence
Jan 26 at 20:10
1
$begingroup$
In summary, all of this can be slightly context dependent of course, but generally speaking what I said before holds. For example, if you have a partial function from $mathbb{N}$ to $mathbb{N}$ and that function happens to be (partial) computable, then by default convention usually when you write a program for it then you would set it up so it doesn't halt on inputs where the function is partial. In practice (say a real world program), if the locations/inputs where the said function is partial are trivial/easy, you might set-up a different convention (but you would have to describe that).
$endgroup$
– SSequence
Jan 26 at 20:33
|
show 9 more comments
$begingroup$
There are two things to separate. First, the definition of functions. A function $f:Arightarrow B$ is a relation $fsubseteq Atimes B$ which is both left-total and right-unique.
Second, the computability of a function. Here one generally considers (partial) functions $f:{Bbb N}_0^krightarrow{Bbb N}_0$. The question is whether there is an algorithm computing the function. By the thesis of Church, the computable functions are exactly those that are partially recursive.
Note that the number of computable functions is denumerable as they correspond to the set of C-programs and the set of C-programs (as words over the keyboard alphabet) is denumerable.
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
$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%2f3076575%2fwell-definedness-of-uncomputable-functions%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$
The busy-beaver-function is well-defined because every halting turing machine can only write a finite number of ones on the tape, hence there must be a champion, and $bb(n)$ is the number of ones this champion writes down.
But the busy-beaver-function is not computable because we cannot determine which turing machines halt and which do not. This (and only this) prevents us from determining the busy-beaver-champion and therefore determining $bb(n)$ in general.
"Computable" means that there is an algorithm being able for every n to either determine $f(n)$ or determine that $f(n)$ is not defined.
"Well-defined" means that there is a description guaranteeing that for every $n$ there is either only one possible value $f(n)$ or that the function is not defined. (It is not necessary that this $f(n)$ can actually be determined , if $f(n)$ is defined.)
answered Jan 19 at 13:54
PeterPeter
48k1139133
$endgroup$
$begingroup$
"Computable" means that there is an algorithm being able to determine f(n) for every n. Not really, partial functions are allowed.
$endgroup$
– Wuestenfux
Jan 20 at 12:20
1
$begingroup$
@Peter I think using computable for a program halting on all inputs is fine. I think it is quite commonly used. For example, the following are equivalent: (a1) computable (a2) recursive (a3) total computable (a4) total recursive. Similarly, the following are also equivalent: (b1) partial computable (b2) partial recursive. Though there are probably some sources that use "computable" to mean "partial computable" and, quite honestly, I think that kind of usage is very confusing (and I very rarely complain about terminology). There are only a couple of exceptions to it (mentioned in next comment).
$endgroup$
– SSequence
Jan 26 at 20:04
1
$begingroup$
Sometimes when people say "collection of computable functions", it can mean "collection of partial computable functions". Otherwise I think the normal association of "computable" with "total computable" is fine. Of course it can be a bit context dependent occasionally so using "total computable" for emphasis can be useful at times. Also, "algorithm" is generally associated with a function halting on all inputs. One thing though, the general convention for a partial computable function is to take it as "undefined" only on those input values for which it does not halt. (cont.)
$endgroup$
– SSequence
Jan 26 at 20:08
1
$begingroup$
So "normally", when a total comptuable function (also called algorithm normally.... unless the context makes it clear that something else is meant) computes a function, the function is presumed to be defined for all values in its domain. Finally note that "partial computable functions" are, by convention, meant to include all functions that may or may not halt on all the inputs. In other words, the collection of partial computable functions contains collection of total compuable functions as strict subset.
$endgroup$
– SSequence
Jan 26 at 20:10
1
$begingroup$
In summary, all of this can be slightly context dependent of course, but generally speaking what I said before holds. For example, if you have a partial function from $mathbb{N}$ to $mathbb{N}$ and that function happens to be (partial) computable, then by default convention usually when you write a program for it then you would set it up so it doesn't halt on inputs where the function is partial. In practice (say a real world program), if the locations/inputs where the said function is partial are trivial/easy, you might set-up a different convention (but you would have to describe that).
$endgroup$
– SSequence
Jan 26 at 20:33
|
show 9 more comments
$begingroup$
The busy-beaver-function is well-defined because every halting turing machine can only write a finite number of ones on the tape, hence there must be a champion, and $bb(n)$ is the number of ones this champion writes down.
But the busy-beaver-function is not computable because we cannot determine which turing machines halt and which do not. This (and only this) prevents us from determining the busy-beaver-champion and therefore determining $bb(n)$ in general.
"Computable" means that there is an algorithm being able for every n to either determine $f(n)$ or determine that $f(n)$ is not defined.
"Well-defined" means that there is a description guaranteeing that for every $n$ there is either only one possible value $f(n)$ or that the function is not defined. (It is not necessary that this $f(n)$ can actually be determined , if $f(n)$ is defined.)
answered Jan 19 at 13:54
PeterPeter
48k1139133
$endgroup$
$begingroup$
"Computable" means that there is an algorithm being able to determine f(n) for every n. Not really, partial functions are allowed.
$endgroup$
– Wuestenfux
Jan 20 at 12:20
1
$begingroup$
@Peter I think using computable for a program halting on all inputs is fine. I think it is quite commonly used. For example, the following are equivalent: (a1) computable (a2) recursive (a3) total computable (a4) total recursive. Similarly, the following are also equivalent: (b1) partial computable (b2) partial recursive. Though there are probably some sources that use "computable" to mean "partial computable" and, quite honestly, I think that kind of usage is very confusing (and I very rarely complain about terminology). There are only a couple of exceptions to it (mentioned in next comment).
$endgroup$
– SSequence
Jan 26 at 20:04
1
$begingroup$
Sometimes when people say "collection of computable functions", it can mean "collection of partial computable functions". Otherwise I think the normal association of "computable" with "total computable" is fine. Of course it can be a bit context dependent occasionally so using "total computable" for emphasis can be useful at times. Also, "algorithm" is generally associated with a function halting on all inputs. One thing though, the general convention for a partial computable function is to take it as "undefined" only on those input values for which it does not halt. (cont.)
$endgroup$
– SSequence
Jan 26 at 20:08
1
$begingroup$
So "normally", when a total comptuable function (also called algorithm normally.... unless the context makes it clear that something else is meant) computes a function, the function is presumed to be defined for all values in its domain. Finally note that "partial computable functions" are, by convention, meant to include all functions that may or may not halt on all the inputs. In other words, the collection of partial computable functions contains collection of total compuable functions as strict subset.
$endgroup$
– SSequence
Jan 26 at 20:10
1
$begingroup$
In summary, all of this can be slightly context dependent of course, but generally speaking what I said before holds. For example, if you have a partial function from $mathbb{N}$ to $mathbb{N}$ and that function happens to be (partial) computable, then by default convention usually when you write a program for it then you would set it up so it doesn't halt on inputs where the function is partial. In practice (say a real world program), if the locations/inputs where the said function is partial are trivial/easy, you might set-up a different convention (but you would have to describe that).
$endgroup$
– SSequence
Jan 26 at 20:33
|
show 9 more comments
$begingroup$
The busy-beaver-function is well-defined because every halting turing machine can only write a finite number of ones on the tape, hence there must be a champion, and $bb(n)$ is the number of ones this champion writes down.
But the busy-beaver-function is not computable because we cannot determine which turing machines halt and which do not. This (and only this) prevents us from determining the busy-beaver-champion and therefore determining $bb(n)$ in general.
"Computable" means that there is an algorithm being able for every n to either determine $f(n)$ or determine that $f(n)$ is not defined.
"Well-defined" means that there is a description guaranteeing that for every $n$ there is either only one possible value $f(n)$ or that the function is not defined. (It is not necessary that this $f(n)$ can actually be determined , if $f(n)$ is defined.)
answered Jan 19 at 13:54
PeterPeter
48k1139133
$endgroup$
The busy-beaver-function is well-defined because every halting turing machine can only write a finite number of ones on the tape, hence there must be a champion, and $bb(n)$ is the number of ones this champion writes down.
But the busy-beaver-function is not computable because we cannot determine which turing machines halt and which do not. This (and only this) prevents us from determining the busy-beaver-champion and therefore determining $bb(n)$ in general.
"Computable" means that there is an algorithm being able for every n to either determine $f(n)$ or determine that $f(n)$ is not defined.
"Well-defined" means that there is a description guaranteeing that for every $n$ there is either only one possible value $f(n)$ or that the function is not defined. (It is not necessary that this $f(n)$ can actually be determined , if $f(n)$ is defined.)
answered Jan 19 at 13:54
PeterPeter
48k1139133
edited Jan 20 at 13:07
answered Jan 19 at 13:54
PeterPeter
48k1139133
answered Jan 19 at 13:54
PeterPeter
48k1139133
answered Jan 19 at 13:54
PeterPeter
48k1139133
48k1139133
$begingroup$
"Computable" means that there is an algorithm being able to determine f(n) for every n. Not really, partial functions are allowed.
$endgroup$
– Wuestenfux
Jan 20 at 12:20
1
$begingroup$
@Peter I think using computable for a program halting on all inputs is fine. I think it is quite commonly used. For example, the following are equivalent: (a1) computable (a2) recursive (a3) total computable (a4) total recursive. Similarly, the following are also equivalent: (b1) partial computable (b2) partial recursive. Though there are probably some sources that use "computable" to mean "partial computable" and, quite honestly, I think that kind of usage is very confusing (and I very rarely complain about terminology). There are only a couple of exceptions to it (mentioned in next comment).
$endgroup$
– SSequence
Jan 26 at 20:04
1
$begingroup$
Sometimes when people say "collection of computable functions", it can mean "collection of partial computable functions". Otherwise I think the normal association of "computable" with "total computable" is fine. Of course it can be a bit context dependent occasionally so using "total computable" for emphasis can be useful at times. Also, "algorithm" is generally associated with a function halting on all inputs. One thing though, the general convention for a partial computable function is to take it as "undefined" only on those input values for which it does not halt. (cont.)
$endgroup$
– SSequence
Jan 26 at 20:08
1
$begingroup$
So "normally", when a total comptuable function (also called algorithm normally.... unless the context makes it clear that something else is meant) computes a function, the function is presumed to be defined for all values in its domain. Finally note that "partial computable functions" are, by convention, meant to include all functions that may or may not halt on all the inputs. In other words, the collection of partial computable functions contains collection of total compuable functions as strict subset.
$endgroup$
– SSequence
Jan 26 at 20:10
1
$begingroup$
In summary, all of this can be slightly context dependent of course, but generally speaking what I said before holds. For example, if you have a partial function from $mathbb{N}$ to $mathbb{N}$ and that function happens to be (partial) computable, then by default convention usually when you write a program for it then you would set it up so it doesn't halt on inputs where the function is partial. In practice (say a real world program), if the locations/inputs where the said function is partial are trivial/easy, you might set-up a different convention (but you would have to describe that).
$endgroup$
– SSequence
Jan 26 at 20:33
|
show 9 more comments
$begingroup$
"Computable" means that there is an algorithm being able to determine f(n) for every n. Not really, partial functions are allowed.
$endgroup$
– Wuestenfux
Jan 20 at 12:20
1
$begingroup$
@Peter I think using computable for a program halting on all inputs is fine. I think it is quite commonly used. For example, the following are equivalent: (a1) computable (a2) recursive (a3) total computable (a4) total recursive. Similarly, the following are also equivalent: (b1) partial computable (b2) partial recursive. Though there are probably some sources that use "computable" to mean "partial computable" and, quite honestly, I think that kind of usage is very confusing (and I very rarely complain about terminology). There are only a couple of exceptions to it (mentioned in next comment).
$endgroup$
– SSequence
Jan 26 at 20:04
1
$begingroup$
Sometimes when people say "collection of computable functions", it can mean "collection of partial computable functions". Otherwise I think the normal association of "computable" with "total computable" is fine. Of course it can be a bit context dependent occasionally so using "total computable" for emphasis can be useful at times. Also, "algorithm" is generally associated with a function halting on all inputs. One thing though, the general convention for a partial computable function is to take it as "undefined" only on those input values for which it does not halt. (cont.)
$endgroup$
– SSequence
Jan 26 at 20:08
1
$begingroup$
So "normally", when a total comptuable function (also called algorithm normally.... unless the context makes it clear that something else is meant) computes a function, the function is presumed to be defined for all values in its domain. Finally note that "partial computable functions" are, by convention, meant to include all functions that may or may not halt on all the inputs. In other words, the collection of partial computable functions contains collection of total compuable functions as strict subset.
$endgroup$
– SSequence
Jan 26 at 20:10
1
$begingroup$
In summary, all of this can be slightly context dependent of course, but generally speaking what I said before holds. For example, if you have a partial function from $mathbb{N}$ to $mathbb{N}$ and that function happens to be (partial) computable, then by default convention usually when you write a program for it then you would set it up so it doesn't halt on inputs where the function is partial. In practice (say a real world program), if the locations/inputs where the said function is partial are trivial/easy, you might set-up a different convention (but you would have to describe that).
$endgroup$
– SSequence
Jan 26 at 20:33
$begingroup$
"Computable" means that there is an algorithm being able to determine f(n) for every n. Not really, partial functions are allowed.
$endgroup$
– Wuestenfux
Jan 20 at 12:20
$begingroup$
"Computable" means that there is an algorithm being able to determine f(n) for every n. Not really, partial functions are allowed.
$endgroup$
– Wuestenfux
Jan 20 at 12:20
1
1
$begingroup$
@Peter I think using computable for a program halting on all inputs is fine. I think it is quite commonly used. For example, the following are equivalent: (a1) computable (a2) recursive (a3) total computable (a4) total recursive. Similarly, the following are also equivalent: (b1) partial computable (b2) partial recursive. Though there are probably some sources that use "computable" to mean "partial computable" and, quite honestly, I think that kind of usage is very confusing (and I very rarely complain about terminology). There are only a couple of exceptions to it (mentioned in next comment).
$endgroup$
– SSequence
Jan 26 at 20:04
$begingroup$
@Peter I think using computable for a program halting on all inputs is fine. I think it is quite commonly used. For example, the following are equivalent: (a1) computable (a2) recursive (a3) total computable (a4) total recursive. Similarly, the following are also equivalent: (b1) partial computable (b2) partial recursive. Though there are probably some sources that use "computable" to mean "partial computable" and, quite honestly, I think that kind of usage is very confusing (and I very rarely complain about terminology). There are only a couple of exceptions to it (mentioned in next comment).
$endgroup$
– SSequence
Jan 26 at 20:04
1
1
$begingroup$
Sometimes when people say "collection of computable functions", it can mean "collection of partial computable functions". Otherwise I think the normal association of "computable" with "total computable" is fine. Of course it can be a bit context dependent occasionally so using "total computable" for emphasis can be useful at times. Also, "algorithm" is generally associated with a function halting on all inputs. One thing though, the general convention for a partial computable function is to take it as "undefined" only on those input values for which it does not halt. (cont.)
$endgroup$
– SSequence
Jan 26 at 20:08
$begingroup$
Sometimes when people say "collection of computable functions", it can mean "collection of partial computable functions". Otherwise I think the normal association of "computable" with "total computable" is fine. Of course it can be a bit context dependent occasionally so using "total computable" for emphasis can be useful at times. Also, "algorithm" is generally associated with a function halting on all inputs. One thing though, the general convention for a partial computable function is to take it as "undefined" only on those input values for which it does not halt. (cont.)
$endgroup$
– SSequence
Jan 26 at 20:08
1
1
$begingroup$
So "normally", when a total comptuable function (also called algorithm normally.... unless the context makes it clear that something else is meant) computes a function, the function is presumed to be defined for all values in its domain. Finally note that "partial computable functions" are, by convention, meant to include all functions that may or may not halt on all the inputs. In other words, the collection of partial computable functions contains collection of total compuable functions as strict subset.
$endgroup$
– SSequence
Jan 26 at 20:10
$begingroup$
So "normally", when a total comptuable function (also called algorithm normally.... unless the context makes it clear that something else is meant) computes a function, the function is presumed to be defined for all values in its domain. Finally note that "partial computable functions" are, by convention, meant to include all functions that may or may not halt on all the inputs. In other words, the collection of partial computable functions contains collection of total compuable functions as strict subset.
$endgroup$
– SSequence
Jan 26 at 20:10
1
1
$begingroup$
In summary, all of this can be slightly context dependent of course, but generally speaking what I said before holds. For example, if you have a partial function from $mathbb{N}$ to $mathbb{N}$ and that function happens to be (partial) computable, then by default convention usually when you write a program for it then you would set it up so it doesn't halt on inputs where the function is partial. In practice (say a real world program), if the locations/inputs where the said function is partial are trivial/easy, you might set-up a different convention (but you would have to describe that).
$endgroup$
– SSequence
Jan 26 at 20:33
$begingroup$
In summary, all of this can be slightly context dependent of course, but generally speaking what I said before holds. For example, if you have a partial function from $mathbb{N}$ to $mathbb{N}$ and that function happens to be (partial) computable, then by default convention usually when you write a program for it then you would set it up so it doesn't halt on inputs where the function is partial. In practice (say a real world program), if the locations/inputs where the said function is partial are trivial/easy, you might set-up a different convention (but you would have to describe that).
$endgroup$
– SSequence
Jan 26 at 20:33
|
show 9 more comments
$begingroup$
There are two things to separate. First, the definition of functions. A function $f:Arightarrow B$ is a relation $fsubseteq Atimes B$ which is both left-total and right-unique.
Second, the computability of a function. Here one generally considers (partial) functions $f:{Bbb N}_0^krightarrow{Bbb N}_0$. The question is whether there is an algorithm computing the function. By the thesis of Church, the computable functions are exactly those that are partially recursive.
Note that the number of computable functions is denumerable as they correspond to the set of C-programs and the set of C-programs (as words over the keyboard alphabet) is denumerable.
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
$endgroup$
add a comment |
$begingroup$
There are two things to separate. First, the definition of functions. A function $f:Arightarrow B$ is a relation $fsubseteq Atimes B$ which is both left-total and right-unique.
Second, the computability of a function. Here one generally considers (partial) functions $f:{Bbb N}_0^krightarrow{Bbb N}_0$. The question is whether there is an algorithm computing the function. By the thesis of Church, the computable functions are exactly those that are partially recursive.
Note that the number of computable functions is denumerable as they correspond to the set of C-programs and the set of C-programs (as words over the keyboard alphabet) is denumerable.
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
$endgroup$
add a comment |
$begingroup$
There are two things to separate. First, the definition of functions. A function $f:Arightarrow B$ is a relation $fsubseteq Atimes B$ which is both left-total and right-unique.
Second, the computability of a function. Here one generally considers (partial) functions $f:{Bbb N}_0^krightarrow{Bbb N}_0$. The question is whether there is an algorithm computing the function. By the thesis of Church, the computable functions are exactly those that are partially recursive.
Note that the number of computable functions is denumerable as they correspond to the set of C-programs and the set of C-programs (as words over the keyboard alphabet) is denumerable.
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
$endgroup$
There are two things to separate. First, the definition of functions. A function $f:Arightarrow B$ is a relation $fsubseteq Atimes B$ which is both left-total and right-unique.
Second, the computability of a function. Here one generally considers (partial) functions $f:{Bbb N}_0^krightarrow{Bbb N}_0$. The question is whether there is an algorithm computing the function. By the thesis of Church, the computable functions are exactly those that are partially recursive.
Note that the number of computable functions is denumerable as they correspond to the set of C-programs and the set of C-programs (as words over the keyboard alphabet) is denumerable.
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
edited Jan 21 at 9:34
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
answered Jan 20 at 12:41
WuestenfuxWuestenfux
4,7311513
4,7311513
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%2f3076575%2fwell-definedness-of-uncomputable-functions%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$
Assuming you are not an ultra-finitist, the busy beaver function is definitely well-defined mathematically. Well-definedness as an integer-valued function is not the same as being uncomputable
$endgroup$
– Brevan Ellefsen
Jan 17 at 4:30
$begingroup$
You are able to always tell which number I should bigger, assuming a universe with nigh infinite data storage and assuming you have a lot of spare time (and I mean a lot)...
$endgroup$
– L. McDonald
Jan 19 at 9:25
$begingroup$
@L.McDonald This depends on what you mean by 'given two numbers'. If the meaning is 'given two properties that each provably define a unique number', then it is not necessarily effectively decidable which number is bigger.
$endgroup$
– spaceisdarkgreen
Jan 19 at 19:20