 Quote by Strill
What do you mean by "Completely uncomputable"? Do you mean that it cannot be computed for all Turing machines, that it cannot be computed for some Turing machines, or that it cannot be computed for a specific Turing machine? Because for a Turing machine without a rule to terminate, this function would always equal 1.
I get the feeling that this is only uncomputable because it's been defined so as to exclude some of the variables on which its result depends.
|
I was slightly imprecise, because I thought the context was obvious. I mean a Universal Turing Machine with at least one FINAL state.
That it is uncomputable, in principle, by any algorithm, is a fundamental result in computer science. I assumed you would be familiar with this - the example was meant to show you already knew an example of an uncomputable function, that is never the less well defined.