News for hackers. Stuff that matters.

A comment on Non-Universality in Computation: The Myth of the Universal Computer. Parent comment

Re:Non-Universality in Computation: The Myth of the Universa... by marksutherland on Thursday April 16, 2009 @04:24PM (#565836)
He's restricting the input functions so that they're parameterised by the variable that marks the current state of the computer. In reality this occurs often (the variable represents time) but mathematically there's no need for this. It seems to me that he's refining the model of a computer which we can realistically construct and showing that are even fewer things it can compute than its theoretical brethren.
[ Parent | on HN ]
Re:Non-Universality in Computation: The Myth of the Universa... by davidmathers on Thursday April 16, 2009 @07:26PM (#566099)
Ok, I think I get it. It's really about entropy. When you create a UTM at time t=1 it's only universal at time t=1, because at time t=2 the information content of the universe has increased, and now you have the TM formerly known as universal.

At first it struck me as absurd: "you can't build a computer for functions that don't exist." Um, right. But that's exactly it. Tomorrow there will exist functions that don't exist today.

Or, from the classification/sensor perspective: "choose any number, I can then add 1 to it and my number will be larger than yours." Um, yeah. But again the UTM is part of the universe and therefore can't contain more information than the universe. Tomorrow the quantity of information in the universe will have increased and your formerly universal TM will fail.

The speed issue is kind of a red herring. If you created the ultimate cisc computer that could compute the entire universe in a single clock cycle it would be constrained by size rather than speed. And tomorrow it would fail.

[ Parent | on HN ]
Re:Non-Universality in Computation: The Myth of the Universa... by marksutherland on Friday April 17, 2009 @05:57AM (#566612)
Yup, that's a good way of putting it. So his claim that the CTT is false is misleading. Really he's showing that it doesn't hold for real machines. Perhaps that's not a particularly novel statement but i certainly found it enlightening :)
[ Parent | on HN ]