What would you do with an infinitely fast computer?

[userxp]

This thread seems to be stuck in an infinite loop too.

Perhaps this post from page 5 will spur some new ideas:

Here's a model of an infinitely fast computer that does a fair amount of what people seem to want to do (like exhaustively bruteforce Goldbach by testing every integer sequentially), but avoiding any of the paradoxes or undefined outputs. It's basically just a modified halting oracle.

Take basically any Turing-complete model of computation you like, and augment it with the ability to output a symbol on each computation step to be appended to an output string, or not to output anything on that step.

One model for an infinitely fast machine would then be an oracle that takes an encoding for such a program and an integer n, and returns the nth symbol that would be output by that program, or if the program would never output n symbols in any finite amount of time, then a special symbol to indicate that this is the case. Equivalently, we can have the oracle return the output string of the program, except that if the output string is infinite, we can never query for more than a finite portion of the string in finite time.

So, the output of the program

Code: Select all

for(n=4 ; ; n+=2) {
  if(!can_be_written_as_sum_of_two_primes(n)) {
    puts("Goldbach false.");
    return;
  }
}
puts("Goldbach true.");


when fed to our magic computer would be "Goldbach false." if the conjecture is false, and the empty string if it is true.

If we want to be able to run many infinite loops without having to dovetail the outputs, or to have some of them depend on others, or to properly output "Goldbach true." in the above case if the conjecture is true, then we can take our infinitely fast computer instead to be a Turing machine augmented with the above oracle. Using this model, it's not hard to, say, enumerate the halting (normal) algorithms/machines and their outputs. And of course, if we really want, we can take an oracle for this new machine, and iterate to get more and more powerful machines up the arithmetic hierarchy. Just pick a machine strong enough to run the meta-meta-meta nested infinite looping calculation you want to run.

[WarDaft]

To give more detail on what I mentioned earlier...

Consider a Turing Machine where each step executes twice as fast as the previous step. IE just a Zeno Turing Machine. If we have this machine notify us if it halts at a finite step and do nothing otherwise, we have a halting oracle for any problem in a convenient bounded time of twice the time of a single tape operation. This is no where near good enough.

Let us augment the ZTM with a counter, or set of counters. Whenever a symbol on a tape is changed, the tape's counter is set to N where N is the number of steps that have elapsed when that symbol changes. If there is no last step after which any tape has changed, the ZTM does not output. What we have now is considerably more powerful. We can select a TM with two tapes, which alternates between simulating the first N Turing Machines N steps and running the oracle machine we are interested in on the N steps using the information gathered so far, and outputting whether or not it halted in that simulation to the second tape. If the oracle machine halts given a proper oracle, then for some N this machine will simulate the finite segment of that oracle that the oracle machine we are emulating requires, and if it halts for this value of N, it will halt for every greater value of N as well. If we find that there is some final stage after which the third tape ceases changing, we can simply run the machine that many steps to read the 3rd tape and see what we get.

The important part is that we have constructed a halting oracle not in the machine running the instructions, but in the instructions themselves, and given ourselves a machine that can satisfy the demands therein. These same instructions can be layered further to create an oracle-2 machine by simulating first regular TMs, then larger and larger sets of oracle TMs. We don't even need to use more tapes, we only need to know if the final halting results ever 'settle', the rest can all go on one tape. If we want to simulate regular TMs, oracle machines from the TMs, oracle-2 machines from the oracle machines, oracle-3s from the oracle twos, and so on, then finally an oracle-ω machine which operates on the result-so-far of any of the preceding oracle machines, we can do that too. In fact, we can do this for any computable relation between layers of the oracles. But suppose we were interested in a question which could not be represented by a computable hierarchy of oracles. Perhaps something like "at which layer of the computable oracle hierarchy can we compute mindbogglingly difficult problem X, if any?" A regular TM can only represent so large a relation between various oracle layers. An oracle machine could represent more. Thankfully, we can run oracle machines! They don't need to halt either, we just have to ensure that their settling properties propagate downwards through our layers of simulation. In fact, just in case the hierarchy provided by oracle one machines isn't enough, we can use any of the oracle machines in the computable hierarchy, because we can run any of them. Indeed, we can even reduce machines in the layers of the hierarchy that only oracle machines can describe down to the oracle machines that describe them, which we can then describe with our regular TM.

Whether we can diagonalize across this nesting of the hierarchies that are accessible to us (first the computable hierarchy, then anything computable by anything in the computable hierarchy, then--) with the tools we have at our disposal or not, I am not sure. I doubt it, but you never know.

[Tchiak]

Run bitcoins on it

[pengper]

no doubt about it- calculate pi xD

I'd actually probably shout over to Nasa to abuse OpenCL and set up a site that lets them use some of my processing. I'd also do lotsa Bitcoin mining

[TaylorP]

Assuming that an "infinitely fast computer" means its can do an infinite number of operations per second, wouldn't you generate all of the possible remaning bitcoins instantaneously? I don't remember the number, but its often cited that there's only a certain number of coins that can be generate with the system before some limiting number is reached. You would only have to mine for one instant and you'd be a bit-illionaire.

[Robert'); DROP TABLE *;]

The magic number is 21 million, but bit-mining was discussed earlier and doesn't work because other machines need to verify your calculations. (IIRC)

[MHD]

Actually I just had an interesting idea...
I would find the Busy Beaver numbers. THAT would be useful. Then with a little fiddling, you can make any computer into a pseudo oracle using the assumpion that if a turing machine with N head states runs for more than BB(N) states, it will never halt.

[Robert'); DROP TABLE *;]

You wouldn't be able to decide any TM, though, except on the infinitely fast hardware. (Where you can do it much more easily just by running the program for an infinite time.)

[WarDaft]

It would be utterly impractical for any non-infinitely fast computer. There's a 2 state 6 symbol TM that takes on the order of 10³⁶⁵⁰⁰ steps to halt. There's also a matter of size. Describing the size of BB(100) would not be a simple task, easier to simply list the number of 100 state TMs that halt. You'd be best off seeing if you can find a way to compress a prefix segment of an actual oracle. You have infinite computational resources after all.

The magic number is 21 million, but bit-mining was discussed earlier and doesn't work because other machines need to verify your calculations. (IIRC)

Verify (which is trivial) and accept.

[MonkeyBoy]

Re: the OP...

Mad libs.

[sakay]

Hey Friends,

I liked your thoughts but when i have a chance, than i played the world heavy graphics games on that computer because i love games.

[roundedge]

This seemed relevant:
http://en.wikipedia.org/wiki/Supertask

[Tirian]

I'd also do lotsa Bitcoin mining

The total market cap for bitcoins is 125 million, so that's a pretty small-time gig even if you managed to cash in before the currency crashed from the lack of confidence you introduced. Now, if you cracked Visa's EFT protocol instead, you've got access to trillions.

[Pingouin7]

With an infinitely fast computer, one could brute-force any password instantly.
Just sayan.

[Dason]

With an infinitely fast computer, one could brute-force any password instantly.
Just sayan.

No you couldn't. What are you going to do about simple systems where you're blocked out for a period of time after x number of incorrect guesses? Just sayan.

[sam_i_am]

With an infinitely fast computer, one could brute-force any password instantly.
Just sayan.

You'd also need infinite bandwidth

[Intrigued]

And the server that is handling the log in process would also need to be infinitely fast.

[Quizatzhaderac]

Play dwarf fortress.

Also implement Maxwell's demon somewhere hot for free energy and AC.

[Pingouin7]

And the server that is handling the log in process would also need to be infinitely fast.

Yes, but that's something that many other posters seem to have forgotten too.

[Yakk]

No, not particularly, because you just emulate all realities that match what you are experiencing (using all laws of computation, I mean physics) and find the simplest one consistent with perceptions then extract the password from that one.

(Note: result is limited by quality of sensors you can attach to said computer)

[lorb]

Play dwarf fortress.

[sam_i_am]

[gaurwraith]

I would count all the numbers there are

[lorb]

I would count all the numbers there are

Not possible. There are uncountable many. Even an infinitely fast computer couldn't do this.

[Technical Ben]

Well, if it has infinite memory as well...

[lorb]

Not even in that case. To count something means to map it to the natural numbers. But there are sets of numbers (e.g. the reals) for which no injective function to the naturals exist. (Actually that is one of the definitions of "uncountable" in math.) Even on an infinitely fast computer with infinite memory it's impossible to "count all the numbers there are."

You could also look at it from this angle: Try to come up with an algorithm that takes any real number as input and outputs two different natural numbers for any two different inputs. (Because counting the reals is the same as constructing a list of pairs where every real number is paired to a different natural number such an algorithm must exist if you want to count the reals.)

[elasto]

Aren't you presuming the computer is only aleph₀ly fast? Perhaps it's aleph₁ly fast! Presumably then it could count all the reals in finite time!

[Technical Ben]

I'd just assume by "count all the numbers" they meant 1,2,3,4 etc. Unless they specify counting the reals.
Even then, it's down to the symbolism, right? They could cheat and say "oh, pie is easy, it's exactly C/d" and leave out the numerical representation.

[mr-mitch]

I'd just assume by "count all the numbers" they meant 1,2,3,4 etc. Unless they specify counting the reals.
Even then, it's down to the symbolism, right? They could cheat and say "oh, pie is easy, it's exactly C/d" and leave out the numerical representation.

Not really, because any real number you're able to describe in is countable. There are real numbers that you can't describe.

[EvanED]

Here's another way of looking at the same thing: there are more real numbers than there are finite strings. "It's exactly C/d" is a finite-length string; even if you could use every single finite-length string (there are an infinite number of them...) over A-Z, 0-9, etc., you wouldn't have enough strings to describe every real number. The only way to describe every real number is if you allow yourself to use infinitely-long strings... in which case not only do you have an infinite number of them, but almost all of them are also infinitely long -- so you couldn't even write a single one down!

(That's about as far as I can take the intuition.)

[mr-mitch]

It gets even worse than that. They aren't recognizable by describable turing machines. As soon as you can describe a turing machine that recognises an indescribable number, that number is no longer indescribable (since you've just described it).

So we wouldn't be able to code such a machine. We need an uncountable intelligence, which is probably impossible.

If you think about it, since the reals are the complete metric space of the rationals, then all indescribable numbers have some cauchy sequence s_n. If given the first k, s_k you can compute s_k+1 (WLOG because if adjacent terms converge then terms spaced by some arbitrary amount also start to converge) then we have described the number and so by contradiction the number wasn't indescribable. So if you had some algorithm J that computed an indescribable number on our machine, then we can form a cauchy sequence that converges (by having s_n be the number with n digits).

So even our infinitely fast computer can't count the real numbers, if it makes discrete transitions (with 0 execution time). It'd have to make some kind of transition that ... is indescribable.

[lorb]

Aren't you presuming the computer is only aleph₀ly fast? Perhaps it's aleph₁ly fast! Presumably then it could count all the reals in finite time!

No. As others already have pointed out: It's not even possible to write the program that could count the reals.

I'd just assume by "count all the numbers" they meant 1,2,3,4 etc. Unless they specify counting the reals.

_all_ numbers sounds to me like every number that exists. Including reals and complex numbers and everything else there is.

[Xenomortis]

There exist real numbers that cannot be computed.
A computable number c is a number for which there exists a function f with codmain in the rationals (that can be computed by a Turing machine) such that:
for any ε < 0, there exists n>0 such that |f(k) - c| < ε for some input k.
Furthermore, the set of all computable numbers is countable. Hence the set of all non-computable numbers is not countable.

So not only do you have numbers that cannot be approximated and hence calculated as a limit by a Turing machine (would an infinitely fast one alleviate that?) but there are more of them than you can count!

Basically, the best you can do with a Turing machine is count a countable set. In fact, that's all you can count, by definition. And if you think you've all the reals, I have Cantor's diagonal argument as backup.

[phlip]

I'd just assume by "count all the numbers" they meant 1,2,3,4 etc. Unless they specify counting the reals.

_all_ numbers sounds to me like every number that exists. Including reals and complex numbers and everything else there is.

Just write a program that counts all the ordinals and be done with it...

[Dason]

I would create a universe in which the "I would count all the numbers" joke wasn't so thoroughly destroyed. Good job guys. Good job.

[dudiobugtron]

Would you be able to generate genuinely random numbers with this computer?

And if you could, then couldn't you just tell it to keep generating random numbers? If you did, would it be able to generate all of them?

Also, why can't we just write a program which does something once for each r in R, instead of for each n in Z⁺? Or once for each r in [0,1) if you want a starting point.

[PM 2Ring]

Also, why can't we just write a program which does something once for each r in R, instead of for each n in Z⁺? Or once for each r in [0,1) if you want a starting point.

As Xenomortis said, "if you think you've all the reals, I have Cantor's diagonal argument as backup".

Any program that purportedly generates all the reals has to do so in some sequence, i.e., it creates a list of reals. And any list of reals is susceptible to Cantor diagonalization.

[dudiobugtron]

As Xenomortis said, "if you think you've all the reals, I have Cantor's diagonal argument as backup".

Any program that purportedly generates all the reals has to do so in some sequence, i.e., it creates a list of reals. And any list of reals is susceptible to Cantor diagonalization.

Any countably infinite list of reals is susceptible to Cantor diagonalisation. An uncountably infinite list containing all of the reals wouldn't be, though. If the program only does countably infinite steps, then sure it won't generate all of the reals. However, it may be able to generate all of the reals after doing O(|R|) steps.

[phlip]

You just need to throw out all your ideas of iterative programming, and use a different model where it's even meaningful to ask what happens if the program has to run for uncountably-many steps. Maybe some functional variant, where you could write

Code: Select all

allReals = {- some definition -}

squaredReals = map (\x -> x*x) allReals
positiveReals = filter (>=0) allReals

assert (squaredReals == positiveReals)

Or maybe something entirely different.

[Xenomortis]

As Xenomortis said, "if you think you've all the reals, I have Cantor's diagonal argument as backup".

Any program that purportedly generates all the reals has to do so in some sequence, i.e., it creates a list of reals. And any list of reals is susceptible to Cantor diagonalization.

Any countably infinite list of reals is susceptible to Cantor diagonalisation. An uncountably infinite list containing all of the reals wouldn't be, though. If the program only does countably infinite steps, then sure it won't generate all of the reals. However, it may be able to generate all of the reals after doing O(|R|) steps.

How do you propose to get an uncountable list?
We are talking about a computer; it calculates things step by step. The term "uncountable" doesn't fit in anywhere.

You just need to throw out all your ideas of iterative programming, and use a different model where it's even meaningful to ask what happens if the program has to run for uncountably-many steps. Maybe some functional variant, where you could write

Code: Select all

allReals = {- some definition -}

squaredReals = map (\x -> x*x) allReals
positiveReals = filter (>=0) allReals

assert (squaredReals == positiveReals)

Or maybe something entirely different.

So... exactly what we do in Mathematics? And never actually generate a list of reals.