For a given algorithm (eg reverse the items in this list) and a given type of Turing machine (eg the 3-state 2-symbol busy beaver reduced to 5-tuples) - is there a single simplest way that this algorithm can be represented?
(This thread on LTU seems to suggest there are differences of opinion about what representing an algorithm on the Turing machine boils down to.)
It is not the algorithms that are represented in different ways, but input and output. Depending on how the input is encoded, a given problem might be hard or easy. To take a trivial example, consider the following encoding of Turing machines:
A turing machine $T$ is represented by a number of the form $2 n + b$ where $n$ such that the binary digit expansion of $n$ gives a description of $T$'s program (encoded in a reasonable way). The number $b$ is $1$ if $T$ halts when run on empty input and $0$ otherwise.
With this encoding of Turing machines the halting problem becomes very easily computable. Given a description of Turing machine, just look at the lowest bit to determine whether the machine stops.
The moral of the story is that encoding of data is meaningless until we also specify what sort of structure we are trying to encode, i.e., which operations on data are supposed to be computable. (In the case of Turing machines it is known that the relevant operations are those of the s-m-n and u-t-m theorems, which fail for the silly encoding above.)
In case we worry about computational complexity we also need to require that the data are suitably "compressed", for example, if the input to an algorithm is a number $n$, it should be written with input of size $O(\log n)$, otherwise we can artificially "boost" the efficiency of the algorithm by writing down input in a very inefficient way.
If we work with the usual Turing machines then all reasonable ways of representing data will be equivalent (even polynomial-time convertible). But with very small Turing machines one might be forced to represent inputs in very strange ways because the machine will lack the power to recode its input in whatever form is needed. Under such circumstances people might disagree what is a reasonable way of encoding input. For example, may the input be repeated twice (suppose the machine lacks the ability to go backwards but it needs to read the input twice to do its job)? May the input be repeated infinitely many times? If we impose no restrictions on how the input is presented to the machine, then the input itself might already contain the answer that the machine is supposedly computing (witness the example of the Halting problem above). Sometimes it is hard to tell whether a given representation is "hiding" extra information. An infamous example of this was the solution to the Wolfram 2,3 Turing machine research prize where the input tape had to contain an infinite repeating pattern in order for the machine to work correctly. I suggest you look at the archives of the Foundations of mathematics mailing list for a detailed discussion about the 2,3 prize and about how even minor changes in input representations can cause big jumps in the computational power of a machine. The relevant threads are:
The short answer to your question is, yes. Once you fix a particular encoding scheme for your TM and your inputs and outputs, then there is a smallest TM that will compute your function. There may be multiple "smallest" TMs (of some size, say, k symbols), and if you want your choice to be unique, you could just choose the lexicographically first such TM. Determining what this size k happens to be is undecidable in general, though. This is essentially what Kolmogorov Complexity is all about, except that there the desired algorithm is something specific--what is the smallest TM that will output string x, starting with a blank input tape.
I can't comment on the discussion at LTU, except that it seems to be more focused on technical limitations of the lambda-calculus than on ambiguities about TM encodings.
I think I'm going to take exception to Andrej's reply to your question. Placing an answer to the halting question, or otherwise supplying the answer to the problem being input on the input itself, is a form of a promise problem. The TM has no way of verifying the input--and if the input is "lying" then the TM is free to output whatever it wants. So this doesn't really address the question at hand. Likewise with the issue of Wolfram's minimalist machines. When deciding whether those are Turing-equivalent or not, the question of how much one is allowed to massage the input becomes key. But I wouldn't consider those machines to be TMs in the first place. All of this falls under the stipulation, "once you fix a particular encoding scheme...", and from the way you phrased your question it seems like you are also making this stipulation.
If my understanding of your question is correct, You want an algorithm to reverse a set of items in a list for one specific Turing machine. An algorithm is the Transition function that solves the problem. There are many representations for the same algorithm. They differ in terms of simplicity of their Transition function. So, there is no way to find the simplest representation of a given algorithm (if you mean by "simple" the size of the transition table representing the transition function). It depends on the creativity of the programmer.
