My confusion stems from this weird dichotomy[1] that basically everything we can compute in the real world can be computed by a finite state automaton, because our world does not contain infinite memory tapes (as far as I know from the probabilistic evidence I was able to gather). But (for convenience?), mathematicians/computer scientists use Turing machines/Lambda Calculus/(your favorite programming language) for most purposes instead to model things, even though they have these really peculiar undecidability properties.
1) Imagine if the whole of the world was a giant, spherical game of life board. The memory isn’t infinite, but it continues to advance by the rules as long as the sun burns.
2) I’ve seen an argument for doing this along the lines of ‘Allowing for infinite, means that if someone comes up with a faster (that is, finite) way of calculating something then it may still have already been reasoned about before.’
Yes, I already knew that, thank you! But why should I care if I can calculate it to an arbitrary/sufficient precision? [5]
Do you care about whether pi^pi is an ‘irrational’ number?
Why is infinite tape required for undecidability to be an issue?
Imagine if the whole of the world was a giant, spherical game of life board. The memory isn’t infinite, but it continues to advance by the rules as long as the sun burns.
Yeah, that makes sense to me.
Why is infinite tape required for undecidability to be an issue?
Because otherwise I can list all the states and transitions. Take your game of life board: We don’t get an issue like a halting problem: if you have a finite game of life, with n cells then there exist 2^n possible states, since the game is deterministic, it must repeat after at least 2^n steps in exactly the same sequence of states (halting in this universe might be interpreted as the same step repeating over and over, which is rather rare in the game of life I believe). Now we compute this sequence from within an even bigger game of life. The “real” problem is that the number of possible states is growing exponentially and there is no even bigger version of our universe to turn to, which is why we can’t even solve chess. As TAG highlighted in his comment, in some sense chess (at least currently) is undecidable for us (just not in the very rigorous sense).
I’ve seen an argument for doing this along the lines of ‘Allowing for infinite, means that if someone comes up with a faster (that is, finite) way of calculating something then it may still have already been reasoned about before.’
Hm… I definitely associate rationals with “the numbers my computer has problems printing or representing internally”. I guess the part why I care is the “representing internally”-part of the association. Now I don’t know, but I could totally see someone having figured out a way to neatly work with some important irrational numbers, at least to some degree, since people can obviously do it and somehow have been able to show that e^(i*pi) is rational. I guess there is probably a neat way to work with infinite series internally?
If a number has an infinite decimal.expansion, it is irrational, and if there is a finite programme that spits out the digits indefinitely, then it’s computable. There is a countable infinity of programmes, but an uncountable infinity of irrational.numbers, so most irrational numbers are uncomputable.
I definitely associate rationals with “the numbers my computer has problems printing or representing internally
You seem to be thinking in terms of fixed length representations. Although widely used , they are not essential to computation, and don’t feature in theoretical
computer science.
(Sorry my Bad. I meant irrational in the previous comment) Yeah, I get that you can do it differently. I meant that you can’t just naively store all the digits. Did minimal googeling and and found the Wikipedia article on computable numbers and it lists all kinds of representations that I would never have thought of.
1) Imagine if the whole of the world was a giant, spherical game of life board. The memory isn’t infinite, but it continues to advance by the rules as long as the sun burns.
2) I’ve seen an argument for doing this along the lines of ‘Allowing for infinite, means that if someone comes up with a faster (that is, finite) way of calculating something then it may still have already been reasoned about before.’
Do you care about whether pi^pi is an ‘irrational’ number?
Why is infinite tape required for undecidability to be an issue?
Yeah, that makes sense to me.
Because otherwise I can list all the states and transitions. Take your game of life board: We don’t get an issue like a halting problem: if you have a finite game of life, with n cells then there exist 2^n possible states, since the game is deterministic, it must repeat after at least 2^n steps in exactly the same sequence of states (halting in this universe might be interpreted as the same step repeating over and over, which is rather rare in the game of life I believe). Now we compute this sequence from within an even bigger game of life. The “real” problem is that the number of possible states is growing exponentially and there is no even bigger version of our universe to turn to, which is why we can’t even solve chess. As TAG highlighted in his comment, in some sense chess (at least currently) is undecidable for us (just not in the very rigorous sense).
Yeah, that is probably a good reason to do it. The first time I stumbled upon this was probably a semitechnical introductory dialogue to solomonoff induction.
Damn. Yes? I feel caught.
But in another sense, what would it mean for a number to be irrational if I could compute it?
The meaning remains the same. Or are you asking how much it matters?
Hm… I definitely associate rationals with “the numbers my computer has problems printing or representing internally”. I guess the part why I care is the “representing internally”-part of the association. Now I don’t know, but I could totally see someone having figured out a way to neatly work with some important irrational numbers, at least to some degree, since people can obviously do it and somehow have been able to show that e^(i*pi) is rational. I guess there is probably a neat way to work with infinite series internally?
If a number has an infinite decimal.expansion, it is irrational, and if there is a finite programme that spits out the digits indefinitely, then it’s computable. There is a countable infinity of programmes, but an uncountable infinity of irrational.numbers, so most irrational numbers are uncomputable.
You seem to be thinking in terms of fixed length representations. Although widely used , they are not essential to computation, and don’t feature in theoretical computer science.
(Sorry my Bad. I meant irrational in the previous comment) Yeah, I get that you can do it differently. I meant that you can’t just naively store all the digits. Did minimal googeling and and found the Wikipedia article on computable numbers and it lists all kinds of representations that I would never have thought of.