Comment by davidmathers | Hacker News Reader

Comment by davidmathers | Hacker News Reader

Parent Full thread

How is this not complete gibberish? A function is a map from a value (set) to a value (set). The identity/definition of a function is the two values it relates. Values don't change, by definition. All he appears to be saying is that a single computer can't compute multiple functions simultaneously, which would be the non-statement of the century.

Definition of function is basic set theory / category theory: http://planetmath.org/encyclopedia/Image2.html

EDIT: let's say the function computes the average age of all living people. So at time t=1 the domain is people alive at time 1 and at time t=2 the domain is people alive at time 2. He's saying that the input to the function is a variable called "people" which keeps changing, but that's not how it works. The input to a function is always a fixed value. The functions defined at times 1 and 2 are different functions because they're defined on different domains.

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.

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.

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 :)

Reply on news.ycombinator.com