Mixing
What is a good reference for the formal mathematical definition of algorithm and heuristic?
$begingroup$
I am looking for a good reference for the definitions of algorithm and heuristics.
According to Alg1 and
Alg2 the formal definition
uses Turing machines. I think there are equivalent methods, see
Wiki or
J. Flum, Einführung in die mathematische Logik
Is there anything better?
On the other hand, I could not find anything about a formal definition of heuristics.
Does a precise mathematical definition for heuristics exist?
I am looking for a broadly supported reference.
(I hope, something like "Feynman Lectures" or the famous "1905 Einstein" papers exist ;-)).
Comments / questions to the answer @Carl Mummert:
The German Wikipedia states "...using Turing machnines, we can provide
the following formal definition [of algorithm]:
A calculation instruction for solving a problem is an algorithm if and only if there exists an equivalent Turing machine
for this calculation instruction and given any input where a solution to the input exists, this Turing machine halts.
What is wrong with that definition?I looked at the "addition of integers" to understand the differences between "algorithm", "Turing machine"
(="computable function" which has many different "programs" according to @Carl Mummert) and "programs":
Turing machine
Integer input is given in unary notation (0 = B(lank), 1 = 1, 2 = 00, ...)
I consider the example 2+3:
B00a000B => "move zeros from the left to the right "000" and replace "0"/"a" by "B".
Result: 5 = BBBB00000B
Algorithm
I could choose the same as the Turing machine above? What do I miss?
According to the German Wikipedia, this is the same / the definition of algorithm!
Programs
I could use the same as Turing machine above? What do I miss?
logic algorithms
asked Jan 11 at 17:05
ChristophChristoph
1013
$endgroup$
add a comment |
$begingroup$
I am looking for a good reference for the definitions of algorithm and heuristics.
According to Alg1 and
Alg2 the formal definition
uses Turing machines. I think there are equivalent methods, see
Wiki or
J. Flum, Einführung in die mathematische Logik
Is there anything better?
On the other hand, I could not find anything about a formal definition of heuristics.
Does a precise mathematical definition for heuristics exist?
I am looking for a broadly supported reference.
(I hope, something like "Feynman Lectures" or the famous "1905 Einstein" papers exist ;-)).
Comments / questions to the answer @Carl Mummert:
The German Wikipedia states "...using Turing machnines, we can provide
the following formal definition [of algorithm]:
A calculation instruction for solving a problem is an algorithm if and only if there exists an equivalent Turing machine
for this calculation instruction and given any input where a solution to the input exists, this Turing machine halts.
What is wrong with that definition?I looked at the "addition of integers" to understand the differences between "algorithm", "Turing machine"
(="computable function" which has many different "programs" according to @Carl Mummert) and "programs":
Turing machine
Integer input is given in unary notation (0 = B(lank), 1 = 1, 2 = 00, ...)
I consider the example 2+3:
B00a000B => "move zeros from the left to the right "000" and replace "0"/"a" by "B".
Result: 5 = BBBB00000B
Algorithm
I could choose the same as the Turing machine above? What do I miss?
According to the German Wikipedia, this is the same / the definition of algorithm!
Programs
I could use the same as Turing machine above? What do I miss?
logic algorithms
asked Jan 11 at 17:05
ChristophChristoph
1013
$endgroup$
1
$begingroup$
For algorithm, maybe Feynman Lectures On Computation.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:08
$begingroup$
Regarding heuristic, it is difficult... maybe Polya's How to solve it.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:09
$begingroup$
Please don't link to commercial sites.
$endgroup$
– Yves Daoust
Jan 11 at 17:18
add a comment |
$begingroup$
I am looking for a good reference for the definitions of algorithm and heuristics.
According to Alg1 and
Alg2 the formal definition
uses Turing machines. I think there are equivalent methods, see
Wiki or
J. Flum, Einführung in die mathematische Logik
Is there anything better?
On the other hand, I could not find anything about a formal definition of heuristics.
Does a precise mathematical definition for heuristics exist?
I am looking for a broadly supported reference.
(I hope, something like "Feynman Lectures" or the famous "1905 Einstein" papers exist ;-)).
Comments / questions to the answer @Carl Mummert:
The German Wikipedia states "...using Turing machnines, we can provide
the following formal definition [of algorithm]:
A calculation instruction for solving a problem is an algorithm if and only if there exists an equivalent Turing machine
for this calculation instruction and given any input where a solution to the input exists, this Turing machine halts.
What is wrong with that definition?I looked at the "addition of integers" to understand the differences between "algorithm", "Turing machine"
(="computable function" which has many different "programs" according to @Carl Mummert) and "programs":
Turing machine
Integer input is given in unary notation (0 = B(lank), 1 = 1, 2 = 00, ...)
I consider the example 2+3:
B00a000B => "move zeros from the left to the right "000" and replace "0"/"a" by "B".
Result: 5 = BBBB00000B
Algorithm
I could choose the same as the Turing machine above? What do I miss?
According to the German Wikipedia, this is the same / the definition of algorithm!
Programs
I could use the same as Turing machine above? What do I miss?
logic algorithms
asked Jan 11 at 17:05
ChristophChristoph
1013
$endgroup$
I am looking for a good reference for the definitions of algorithm and heuristics.
According to Alg1 and
Alg2 the formal definition
uses Turing machines. I think there are equivalent methods, see
Wiki or
J. Flum, Einführung in die mathematische Logik
Is there anything better?
On the other hand, I could not find anything about a formal definition of heuristics.
Does a precise mathematical definition for heuristics exist?
I am looking for a broadly supported reference.
(I hope, something like "Feynman Lectures" or the famous "1905 Einstein" papers exist ;-)).
Comments / questions to the answer @Carl Mummert:
The German Wikipedia states "...using Turing machnines, we can provide
the following formal definition [of algorithm]:
A calculation instruction for solving a problem is an algorithm if and only if there exists an equivalent Turing machine
for this calculation instruction and given any input where a solution to the input exists, this Turing machine halts.
What is wrong with that definition?I looked at the "addition of integers" to understand the differences between "algorithm", "Turing machine"
(="computable function" which has many different "programs" according to @Carl Mummert) and "programs":
Turing machine
Integer input is given in unary notation (0 = B(lank), 1 = 1, 2 = 00, ...)
I consider the example 2+3:
B00a000B => "move zeros from the left to the right "000" and replace "0"/"a" by "B".
Result: 5 = BBBB00000B
Algorithm
I could choose the same as the Turing machine above? What do I miss?
According to the German Wikipedia, this is the same / the definition of algorithm!
Programs
I could use the same as Turing machine above? What do I miss?
logic algorithms
logic algorithms
asked Jan 11 at 17:05
ChristophChristoph
1013
asked Jan 11 at 17:05
ChristophChristoph
1013
edited Jan 17 at 15:24
Christoph
asked Jan 11 at 17:05
ChristophChristoph
1013
asked Jan 11 at 17:05
ChristophChristoph
1013
asked Jan 11 at 17:05
ChristophChristoph
1013
1013
1
$begingroup$
For algorithm, maybe Feynman Lectures On Computation.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:08
$begingroup$
Regarding heuristic, it is difficult... maybe Polya's How to solve it.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:09
$begingroup$
Please don't link to commercial sites.
$endgroup$
– Yves Daoust
Jan 11 at 17:18
add a comment |
1
$begingroup$
For algorithm, maybe Feynman Lectures On Computation.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:08
$begingroup$
Regarding heuristic, it is difficult... maybe Polya's How to solve it.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:09
$begingroup$
Please don't link to commercial sites.
$endgroup$
– Yves Daoust
Jan 11 at 17:18
1
1
$begingroup$
For algorithm, maybe Feynman Lectures On Computation.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:08
$begingroup$
For algorithm, maybe Feynman Lectures On Computation.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:08
$begingroup$
Regarding heuristic, it is difficult... maybe Polya's How to solve it.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:09
$begingroup$
Regarding heuristic, it is difficult... maybe Polya's How to solve it.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:09
$begingroup$
Please don't link to commercial sites.
$endgroup$
– Yves Daoust
Jan 11 at 17:18
$begingroup$
Please don't link to commercial sites.
$endgroup$
– Yves Daoust
Jan 11 at 17:18
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
There is no single mathematical definition of an "algorithm". There is a well accepted definition of a computable function - the class of computable functions can be defined in terms of Turing machines, register machines, and many other models of computation.
However, this does not answer the problem of defining an "algorithm", because every computable function has many different programs to compute it, and it is not clear how to tell whether two programs use the same algorithm or use different algorithms.
This is also why "program" or "Turing machine" cannot be used as a definition of an algorithm. A key aspect of the term "algorithm" is that the same algorithm can be turned into many different programs.
So the definition of "computable function" is too coarse to capture the meaning of "algorithm", while the definition of "program" is too fine.
In computability theory and computer science, "algorithm" is used only as an informal term, or to refer to a specific set of instructions. In other words, we know particular algorithms, such as Djiktra's algorithm, but we don't have a definition of "algorithm" in general.
For a partial list of attempts to define "algorithm", see algorithm characterizations on Wikipedia. At least 15 different attempts are described there.
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
$endgroup$
2
$begingroup$
Another way to understand why it's hard to define "algorithm" is to look to Quine's slogan "no entity without identity". The slogan means, in this case, that any precise formal definition of an algorithm would need to provide a concrete way of telling whether two algorithms are the same algorithm or are genuinely different algorithms. There is no generally accepted criterion of that sort, apart from ones that are too coarse or too fine. If we accept Quine's slogan, solving the problem of precisely defining an "algorithm" also requires solving the problem of when two algorithms are the same.
$endgroup$
– Carl Mummert
Jan 11 at 17:56
$begingroup$
Thanks for the effort. I have enough to read :-) is there a book you would recommend? It seems your are talking about things which became basic knowledge...
$endgroup$
– Christoph
Jan 11 at 21:46
$begingroup$
Sorry, but I think I really miss a crucial point - see my edit to the question. Any hint is highly appreciated!
$endgroup$
– Christoph
Jan 17 at 15:25
add a comment |
$begingroup$
A heuristic is usually a "trick" used in an algorithm to improve some of its performance (usually the expected time complexity), and is of the same nature as an algorithm. In this sense, it follows the same formalization.
On the other hand, a heuristic needn't have a rigorous justification, it can be purely intuitive. In this sense, there is nothing you can formalize.
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
$endgroup$
$begingroup$
Is there any reference to a book or an article?
$endgroup$
– Christoph
Jan 11 at 21:51
1
$begingroup$
@Christoph: never seen that. There is no "theory" of heuristics.
$endgroup$
– Yves Daoust
Jan 11 at 21:54
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%2f3070077%2fwhat-is-a-good-reference-for-the-formal-mathematical-definition-of-algorithm-and%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$
There is no single mathematical definition of an "algorithm". There is a well accepted definition of a computable function - the class of computable functions can be defined in terms of Turing machines, register machines, and many other models of computation.
However, this does not answer the problem of defining an "algorithm", because every computable function has many different programs to compute it, and it is not clear how to tell whether two programs use the same algorithm or use different algorithms.
This is also why "program" or "Turing machine" cannot be used as a definition of an algorithm. A key aspect of the term "algorithm" is that the same algorithm can be turned into many different programs.
So the definition of "computable function" is too coarse to capture the meaning of "algorithm", while the definition of "program" is too fine.
In computability theory and computer science, "algorithm" is used only as an informal term, or to refer to a specific set of instructions. In other words, we know particular algorithms, such as Djiktra's algorithm, but we don't have a definition of "algorithm" in general.
For a partial list of attempts to define "algorithm", see algorithm characterizations on Wikipedia. At least 15 different attempts are described there.
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
$endgroup$
2
$begingroup$
Another way to understand why it's hard to define "algorithm" is to look to Quine's slogan "no entity without identity". The slogan means, in this case, that any precise formal definition of an algorithm would need to provide a concrete way of telling whether two algorithms are the same algorithm or are genuinely different algorithms. There is no generally accepted criterion of that sort, apart from ones that are too coarse or too fine. If we accept Quine's slogan, solving the problem of precisely defining an "algorithm" also requires solving the problem of when two algorithms are the same.
$endgroup$
– Carl Mummert
Jan 11 at 17:56
$begingroup$
Thanks for the effort. I have enough to read :-) is there a book you would recommend? It seems your are talking about things which became basic knowledge...
$endgroup$
– Christoph
Jan 11 at 21:46
$begingroup$
Sorry, but I think I really miss a crucial point - see my edit to the question. Any hint is highly appreciated!
$endgroup$
– Christoph
Jan 17 at 15:25
add a comment |
$begingroup$
There is no single mathematical definition of an "algorithm". There is a well accepted definition of a computable function - the class of computable functions can be defined in terms of Turing machines, register machines, and many other models of computation.
However, this does not answer the problem of defining an "algorithm", because every computable function has many different programs to compute it, and it is not clear how to tell whether two programs use the same algorithm or use different algorithms.
This is also why "program" or "Turing machine" cannot be used as a definition of an algorithm. A key aspect of the term "algorithm" is that the same algorithm can be turned into many different programs.
So the definition of "computable function" is too coarse to capture the meaning of "algorithm", while the definition of "program" is too fine.
In computability theory and computer science, "algorithm" is used only as an informal term, or to refer to a specific set of instructions. In other words, we know particular algorithms, such as Djiktra's algorithm, but we don't have a definition of "algorithm" in general.
For a partial list of attempts to define "algorithm", see algorithm characterizations on Wikipedia. At least 15 different attempts are described there.
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
$endgroup$
2
$begingroup$
Another way to understand why it's hard to define "algorithm" is to look to Quine's slogan "no entity without identity". The slogan means, in this case, that any precise formal definition of an algorithm would need to provide a concrete way of telling whether two algorithms are the same algorithm or are genuinely different algorithms. There is no generally accepted criterion of that sort, apart from ones that are too coarse or too fine. If we accept Quine's slogan, solving the problem of precisely defining an "algorithm" also requires solving the problem of when two algorithms are the same.
$endgroup$
– Carl Mummert
Jan 11 at 17:56
$begingroup$
Thanks for the effort. I have enough to read :-) is there a book you would recommend? It seems your are talking about things which became basic knowledge...
$endgroup$
– Christoph
Jan 11 at 21:46
$begingroup$
Sorry, but I think I really miss a crucial point - see my edit to the question. Any hint is highly appreciated!
$endgroup$
– Christoph
Jan 17 at 15:25
add a comment |
$begingroup$
There is no single mathematical definition of an "algorithm". There is a well accepted definition of a computable function - the class of computable functions can be defined in terms of Turing machines, register machines, and many other models of computation.
However, this does not answer the problem of defining an "algorithm", because every computable function has many different programs to compute it, and it is not clear how to tell whether two programs use the same algorithm or use different algorithms.
This is also why "program" or "Turing machine" cannot be used as a definition of an algorithm. A key aspect of the term "algorithm" is that the same algorithm can be turned into many different programs.
So the definition of "computable function" is too coarse to capture the meaning of "algorithm", while the definition of "program" is too fine.
In computability theory and computer science, "algorithm" is used only as an informal term, or to refer to a specific set of instructions. In other words, we know particular algorithms, such as Djiktra's algorithm, but we don't have a definition of "algorithm" in general.
For a partial list of attempts to define "algorithm", see algorithm characterizations on Wikipedia. At least 15 different attempts are described there.
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
$endgroup$
There is no single mathematical definition of an "algorithm". There is a well accepted definition of a computable function - the class of computable functions can be defined in terms of Turing machines, register machines, and many other models of computation.
However, this does not answer the problem of defining an "algorithm", because every computable function has many different programs to compute it, and it is not clear how to tell whether two programs use the same algorithm or use different algorithms.
This is also why "program" or "Turing machine" cannot be used as a definition of an algorithm. A key aspect of the term "algorithm" is that the same algorithm can be turned into many different programs.
So the definition of "computable function" is too coarse to capture the meaning of "algorithm", while the definition of "program" is too fine.
In computability theory and computer science, "algorithm" is used only as an informal term, or to refer to a specific set of instructions. In other words, we know particular algorithms, such as Djiktra's algorithm, but we don't have a definition of "algorithm" in general.
For a partial list of attempts to define "algorithm", see algorithm characterizations on Wikipedia. At least 15 different attempts are described there.
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
edited Jan 11 at 17:39
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
answered Jan 11 at 17:22
Carl MummertCarl Mummert
66.7k7132248
66.7k7132248
2
$begingroup$
Another way to understand why it's hard to define "algorithm" is to look to Quine's slogan "no entity without identity". The slogan means, in this case, that any precise formal definition of an algorithm would need to provide a concrete way of telling whether two algorithms are the same algorithm or are genuinely different algorithms. There is no generally accepted criterion of that sort, apart from ones that are too coarse or too fine. If we accept Quine's slogan, solving the problem of precisely defining an "algorithm" also requires solving the problem of when two algorithms are the same.
$endgroup$
– Carl Mummert
Jan 11 at 17:56
$begingroup$
Thanks for the effort. I have enough to read :-) is there a book you would recommend? It seems your are talking about things which became basic knowledge...
$endgroup$
– Christoph
Jan 11 at 21:46
$begingroup$
Sorry, but I think I really miss a crucial point - see my edit to the question. Any hint is highly appreciated!
$endgroup$
– Christoph
Jan 17 at 15:25
add a comment |
2
$begingroup$
Another way to understand why it's hard to define "algorithm" is to look to Quine's slogan "no entity without identity". The slogan means, in this case, that any precise formal definition of an algorithm would need to provide a concrete way of telling whether two algorithms are the same algorithm or are genuinely different algorithms. There is no generally accepted criterion of that sort, apart from ones that are too coarse or too fine. If we accept Quine's slogan, solving the problem of precisely defining an "algorithm" also requires solving the problem of when two algorithms are the same.
$endgroup$
– Carl Mummert
Jan 11 at 17:56
$begingroup$
Thanks for the effort. I have enough to read :-) is there a book you would recommend? It seems your are talking about things which became basic knowledge...
$endgroup$
– Christoph
Jan 11 at 21:46
$begingroup$
Sorry, but I think I really miss a crucial point - see my edit to the question. Any hint is highly appreciated!
$endgroup$
– Christoph
Jan 17 at 15:25
2
2
$begingroup$
Another way to understand why it's hard to define "algorithm" is to look to Quine's slogan "no entity without identity". The slogan means, in this case, that any precise formal definition of an algorithm would need to provide a concrete way of telling whether two algorithms are the same algorithm or are genuinely different algorithms. There is no generally accepted criterion of that sort, apart from ones that are too coarse or too fine. If we accept Quine's slogan, solving the problem of precisely defining an "algorithm" also requires solving the problem of when two algorithms are the same.
$endgroup$
– Carl Mummert
Jan 11 at 17:56
$begingroup$
Another way to understand why it's hard to define "algorithm" is to look to Quine's slogan "no entity without identity". The slogan means, in this case, that any precise formal definition of an algorithm would need to provide a concrete way of telling whether two algorithms are the same algorithm or are genuinely different algorithms. There is no generally accepted criterion of that sort, apart from ones that are too coarse or too fine. If we accept Quine's slogan, solving the problem of precisely defining an "algorithm" also requires solving the problem of when two algorithms are the same.
$endgroup$
– Carl Mummert
Jan 11 at 17:56
$begingroup$
Thanks for the effort. I have enough to read :-) is there a book you would recommend? It seems your are talking about things which became basic knowledge...
$endgroup$
– Christoph
Jan 11 at 21:46
$begingroup$
Thanks for the effort. I have enough to read :-) is there a book you would recommend? It seems your are talking about things which became basic knowledge...
$endgroup$
– Christoph
Jan 11 at 21:46
$begingroup$
Sorry, but I think I really miss a crucial point - see my edit to the question. Any hint is highly appreciated!
$endgroup$
– Christoph
Jan 17 at 15:25
$begingroup$
Sorry, but I think I really miss a crucial point - see my edit to the question. Any hint is highly appreciated!
$endgroup$
– Christoph
Jan 17 at 15:25
add a comment |
$begingroup$
A heuristic is usually a "trick" used in an algorithm to improve some of its performance (usually the expected time complexity), and is of the same nature as an algorithm. In this sense, it follows the same formalization.
On the other hand, a heuristic needn't have a rigorous justification, it can be purely intuitive. In this sense, there is nothing you can formalize.
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
$endgroup$
$begingroup$
Is there any reference to a book or an article?
$endgroup$
– Christoph
Jan 11 at 21:51
1
$begingroup$
@Christoph: never seen that. There is no "theory" of heuristics.
$endgroup$
– Yves Daoust
Jan 11 at 21:54
add a comment |
$begingroup$
A heuristic is usually a "trick" used in an algorithm to improve some of its performance (usually the expected time complexity), and is of the same nature as an algorithm. In this sense, it follows the same formalization.
On the other hand, a heuristic needn't have a rigorous justification, it can be purely intuitive. In this sense, there is nothing you can formalize.
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
$endgroup$
$begingroup$
Is there any reference to a book or an article?
$endgroup$
– Christoph
Jan 11 at 21:51
1
$begingroup$
@Christoph: never seen that. There is no "theory" of heuristics.
$endgroup$
– Yves Daoust
Jan 11 at 21:54
add a comment |
$begingroup$
A heuristic is usually a "trick" used in an algorithm to improve some of its performance (usually the expected time complexity), and is of the same nature as an algorithm. In this sense, it follows the same formalization.
On the other hand, a heuristic needn't have a rigorous justification, it can be purely intuitive. In this sense, there is nothing you can formalize.
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
$endgroup$
A heuristic is usually a "trick" used in an algorithm to improve some of its performance (usually the expected time complexity), and is of the same nature as an algorithm. In this sense, it follows the same formalization.
On the other hand, a heuristic needn't have a rigorous justification, it can be purely intuitive. In this sense, there is nothing you can formalize.
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
answered Jan 11 at 17:17
Yves DaoustYves Daoust
127k673226
127k673226
$begingroup$
Is there any reference to a book or an article?
$endgroup$
– Christoph
Jan 11 at 21:51
1
$begingroup$
@Christoph: never seen that. There is no "theory" of heuristics.
$endgroup$
– Yves Daoust
Jan 11 at 21:54
add a comment |
$begingroup$
Is there any reference to a book or an article?
$endgroup$
– Christoph
Jan 11 at 21:51
1
$begingroup$
@Christoph: never seen that. There is no "theory" of heuristics.
$endgroup$
– Yves Daoust
Jan 11 at 21:54
$begingroup$
Is there any reference to a book or an article?
$endgroup$
– Christoph
Jan 11 at 21:51
$begingroup$
Is there any reference to a book or an article?
$endgroup$
– Christoph
Jan 11 at 21:51
1
1
$begingroup$
@Christoph: never seen that. There is no "theory" of heuristics.
$endgroup$
– Yves Daoust
Jan 11 at 21:54
$begingroup$
@Christoph: never seen that. There is no "theory" of heuristics.
$endgroup$
– Yves Daoust
Jan 11 at 21:54
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%2f3070077%2fwhat-is-a-good-reference-for-the-formal-mathematical-definition-of-algorithm-and%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
1
$begingroup$
For algorithm, maybe Feynman Lectures On Computation.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:08
$begingroup$
Regarding heuristic, it is difficult... maybe Polya's How to solve it.
$endgroup$
– Mauro ALLEGRANZA
Jan 11 at 17:09
$begingroup$
Please don't link to commercial sites.
$endgroup$
– Yves Daoust
Jan 11 at 17:18