Donald Knuth in the first volume of his book presents a mathematical definition of an algorithm that satisfies the first four criteria for a list of instructions to be an algorithm (finiteness, definiteness, input and output). He defines his fifth criterion as "effectiveness". He explains this to be "computable in principle exactly in a finite amount of time by someone with pencil and paper".
He then gives a method of computation that qualifies for this fifth criterion also. This is a modification of the model that involves symbol manipulation proposed by A.A. Markov. N.J. Cutland in his book "Computability" says on page 65 that "Markov-computability on N (the set of natural numbers) is defined by using some system of representing numbers in the usual way, and thus coincides with the other approaches to computability". This seems to suggest that the class of Markov-computable functions coincides with the class of, for example, Turing-computable functions. This is probably true of Knuth-computable functions also. Nevertheless, it would be nice to have a direct proof that Knuth-computable functions are the same as partial recursive functions.
An exposition of Knuth-computability is given here.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment