4 ms·
> Consider an irrational number, where the fastest possible algorithm (given a standard Turing machine) to compute its nth digit requires (10^(10^100))*(n+1) op
by tromp 2y ago
> Consider an irrational number, where the fastest possible algorithm (given a standard Turing machine) to compute its nth digit requires (10^(10^100))*(n+1) operations
There can be no such number. You can always make a Turing machine output initial digits faster by adding some more states to do so.
- skissane 2y agoYes, if you knew ahead of time that the first digit of some such number happened to be seven, you could just hardcode your program to start with "IF n = 0 THEN RETURN 7". But that's cheating... Let's denote the nth prime by P(n). Now, consider the real number Q, where 0.0 < Q < 1.0, and the nth decimal digit (after the decimal point) of Q, Q(n), is given by Q(n) = P(10^(10^100) + n) mod 10. Q, as defined, is computable, but (unless we discover some mathematical "shortcut" for computing the last digit of a prime number), I doubt we are ever going to know what even its first digit is (well, we know it must be 1, 3, 7 or 9–but which of those four?). And even if some such "shortcut" were discovered, I'm sure someone could cook up another such number for which there is no known "shortcut". How about this: let N(n) be any FNP-complete [FNP is to function problems what NP is to decision problems] computable endofunction of the natural numbers (there are many to choose from, pick any), then define: Q(n) = P(N(10^(10^100) + n)) mod 10 You actually think we'll ever know the first digit of the real number so defined?