3 ms·
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
by Sniffnoy 13y ago
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.
- sp332 13y agoomega == omega^2. They are the same quantity. For every element of omega^2, there is a corresponding unique element of omega.
- adamtj 13y agoActually, no. I just recently read about this. 1 + omega == omega < omega + 1 < omega^2 http://en.wikipedia.org/wiki/Ordinal_number http://en.wikipedia.org/wiki/Ordinal_number
- sp332 13y agoWeird! Thanks for the link!
- wfo 13y agoActually 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.