## What would you do with an infinitely fast computer?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

### Re: What would you do with an infinitely fast computer?

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

Perhaps this post from page 5 will spur some new ideas:
lightvector wrote: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
Ended wrote:
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.
userxp

Posts: 436
Joined: Thu Jul 09, 2009 12:40 pm UTC

### Re: What would you do with an infinitely fast computer?

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1553
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: What would you do with an infinitely fast computer?

Run bitcoins on it
Tchiak

Posts: 27
Joined: Fri Aug 22, 2008 10:01 pm UTC

### Re: What would you do with an infinitely fast computer?

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
pengper

Posts: 3
Joined: Wed Jul 20, 2011 1:32 pm UTC
Location: The third box to the right. I'm riding the spider ;)

### Re: What would you do with an infinitely fast computer?

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.

TaylorP

Posts: 60
Joined: Mon Jul 18, 2011 5:08 am UTC
Location: Ontario, Canada

### Re: What would you do with an infinitely fast computer?

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)
...And that is how we know the Earth to be banana-shaped.

Robert'); DROP TABLE *;

Posts: 658
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

### Re: What would you do with an infinitely fast computer?

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.
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

MHD

Posts: 631
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

### Re: What would you do with an infinitely fast computer?

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.)
...And that is how we know the Earth to be banana-shaped.

Robert'); DROP TABLE *;

Posts: 658
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

### Re: What would you do with an infinitely fast computer?

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 1036500 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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1553
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: What would you do with an infinitely fast computer?

Re: the OP...

Mad libs.

MonkeyBoy

Posts: 55
Joined: Tue Jun 28, 2011 7:28 am UTC

### Re: What would you do with an infinitely fast computer?

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.
sakay

Posts: 1
Joined: Fri Sep 09, 2011 8:44 pm UTC

### Re: What would you do with an infinitely fast computer?

roundedge

Posts: 167
Joined: Wed Jun 20, 2007 3:53 am UTC
Location: White Rock, BC, Canada

### Re: What would you do with an infinitely fast computer?

pengper wrote: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.
Tirian

Posts: 1557
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: What would you do with an infinitely fast computer?

With an infinitely fast computer, one could brute-force any password instantly.
Just sayan.
Dason wrote:
Kewangji wrote:I confess I am actually scared of peanuts, and tend to avoid them, given how lethal they are to some people.

I'm not. I do my part in the fight against peanuts by destroying them with my powerful teeth. Take that peanut! How does being digested feel!?
Pingouin7

Posts: 80
Joined: Thu Oct 27, 2011 4:50 pm UTC
Location: ~/

### Re: What would you do with an infinitely fast computer?

Pingouin7 wrote: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.
double epsilon = -.0000001;

Dason

Posts: 1274
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

### Re: What would you do with an infinitely fast computer?

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

You'd also need infinite bandwidth

sam_i_am

Posts: 563
Joined: Mon Jun 18, 2012 3:38 pm UTC
Location: Urbana, Illinois, USA

### Re: What would you do with an infinitely fast computer?

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

Posts: 450
Joined: Tue May 11, 2010 3:47 pm UTC

### Re: What would you do with an infinitely fast computer?

Play dwarf fortress.

Also implement Maxwell's demon somewhere hot for free energy and AC.
Modern art and philosophy will instead be described to as "Marklar', which is much less silly.
Quizatzhaderac

Posts: 571
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

### Re: What would you do with an infinitely fast computer?

Intrigued wrote: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.
Dason wrote:
Kewangji wrote:I confess I am actually scared of peanuts, and tend to avoid them, given how lethal they are to some people.

I'm not. I do my part in the fight against peanuts by destroying them with my powerful teeth. Take that peanut! How does being digested feel!?
Pingouin7

Posts: 80
Joined: Thu Oct 27, 2011 4:50 pm UTC
Location: ~/

### Re: What would you do with an infinitely fast computer?

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)

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10207
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: What would you do with an infinitely fast computer?

Quizatzhaderac wrote:Play dwarf fortress.
Please be gracious in judging my english. (I am not a native speaker/writer.)
lorb

Posts: 153
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

### Re: What would you do with an infinitely fast computer?

sam_i_am

Posts: 563
Joined: Mon Jun 18, 2012 3:38 pm UTC
Location: Urbana, Illinois, USA

### Re: What would you do with an infinitely fast computer?

I would count all the numbers there are
I am a lvl 89 sword barb

gaurwraith

Posts: 286
Joined: Fri Jul 27, 2007 3:56 pm UTC

### Re: What would you do with an infinitely fast computer?

gaurwraith wrote:I would count all the numbers there are

Not possible. There are uncountable many. Even an infinitely fast computer couldn't do this.
Please be gracious in judging my english. (I am not a native speaker/writer.)
lorb

Posts: 153
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

### Re: What would you do with an infinitely fast computer?

Well, if it has infinite memory as well...
It's all physics and stamp collecting.
It's not a particle or a wave. It's just an exchange.
Technical Ben

Posts: 2989
Joined: Tue May 27, 2008 10:42 pm UTC

### Re: What would you do with an infinitely fast computer?

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.)
Please be gracious in judging my english. (I am not a native speaker/writer.)
lorb

Posts: 153
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

### Re: What would you do with an infinitely fast computer?

Aren't you presuming the computer is only aleph0ly fast? Perhaps it's aleph1ly fast! Presumably then it could count all the reals in finite time!
elasto

Posts: 1121
Joined: Mon May 10, 2010 1:53 am UTC

### Re: What would you do with an infinitely fast computer?

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.
It's all physics and stamp collecting.
It's not a particle or a wave. It's just an exchange.
Technical Ben

Posts: 2989
Joined: Tue May 27, 2008 10:42 pm UTC

### Re: What would you do with an infinitely fast computer?

Technical Ben wrote: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.
mr-mitch

Posts: 473
Joined: Sun Jul 05, 2009 6:56 pm UTC

### Re: What would you do with an infinitely fast computer?

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.)
EvanED

Posts: 3929
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

### Re: What would you do with an infinitely fast computer?

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 sn. If given the first k, sk you can compute sk+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 sn 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.
mr-mitch

Posts: 473
Joined: Sun Jul 05, 2009 6:56 pm UTC

### Re: What would you do with an infinitely fast computer?

elasto wrote:Aren't you presuming the computer is only aleph0ly fast? Perhaps it's aleph1ly 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.

Technical Ben wrote: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.
Please be gracious in judging my english. (I am not a native speaker/writer.)
lorb

Posts: 153
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

### Re: What would you do with an infinitely fast computer?

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.

Xenomortis
Not actually a special flower.

Posts: 671
Joined: Thu Oct 11, 2012 8:47 am UTC

### Re: What would you do with an infinitely fast computer?

lorb wrote:
Technical Ben wrote: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...
While no one overhear you quickly tell me not cow cow.
but how about watch phone?

phlip
Restorer of Worlds

Posts: 6958
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: What would you do with an infinitely fast computer?

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.
double epsilon = -.0000001;

Dason

Posts: 1274
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

### Re: What would you do with an infinitely fast computer?

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.

dudiobugtron

Posts: 1082
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Re: What would you do with an infinitely fast computer?

dudiobugtron wrote: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.

PM 2Ring

Posts: 2959
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: What would you do with an infinitely fast computer?

PM 2Ring wrote: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.

dudiobugtron

Posts: 1082
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Re: What would you do with an infinitely fast computer?

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) allRealspositiveReals = filter (>=0) allRealsassert (squaredReals == positiveReals)`

Or maybe something entirely different.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?

phlip
Restorer of Worlds

Posts: 6958
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: What would you do with an infinitely fast computer?

dudiobugtron wrote:
PM 2Ring wrote: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.

phlip wrote: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) allRealspositiveReals = filter (>=0) allRealsassert (squaredReals == positiveReals)`

Or maybe something entirely different.

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

Xenomortis
Not actually a special flower.

Posts: 671
Joined: Thu Oct 11, 2012 8:47 am UTC

PreviousNext

Return to Computer Science

### Who is online

Users browsing this forum: No registered users and 3 guests