Re:Is There Anything Beyond Quantum Computing?
by Sniffnoy on Friday April 11, 2014 @03:41PM
(#7575107)
This isn't about cardinality, though, this is about number of steps, which is more properly measured with ordinal numbers. I'm not familiar with the theory of infinite-time Turing machines, but it's at least plausible that there are things you can do with omega^2 steps (or larger countable ordinals) that you couldn't do with only omega steps.
[ Parent
| on HN ]
Re:Is There Anything Beyond Quantum Computing?
by sp332 on Friday April 11, 2014 @03:56PM
(#7575201)
omega == omega^2. They are the same quantity. For every element of omega^2, there is a corresponding unique element of omega.
Re:Is There Anything Beyond Quantum Computing?
by adamtj on Friday April 11, 2014 @04:46PM
(#7575528)
Actually, no. I just recently read about this.
1 + omega == omega < omega + 1 < omega^2
Re:Is There Anything Beyond Quantum Computing?
by sp332 on Friday April 11, 2014 @04:59PM
(#7575600)
Weird! Thanks for the link!
Actually you are both right -- omega and omega + 1 (or omega^2) have the same 'number' of elements (there is a one to one correspondence) but the correspondence will not be (can not be) order-preserving. Ordinals are a natural extension of the natural numbers. If you take the natural numbers and add a new element that's bigger than all of them then you get a new structure (called omega + 1) which has the same size as the normal natural numbers, but has one new element which is order-distinguishable from all our normal numbers. Some ordinals, which correspond to a jump in 'size' (like 2^omega) are special and called cardinal numbers.