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?
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.