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

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

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

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

All you need is some parallel processing. Uncountably infinitely many processes running in parallel, that is.

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

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

- The first thread creates a list of reals starting 0.1...
- The second thread creates a list of reals starting 0.2...
- ...
- The tenth thread creates a list of reals starting 0.0...
Then combine the results.

Each thread, to create its complete list, itself creates ten subthreads, recursively forever. But, since it's infinitely fast, it can finish all the threads and return the results!

To create all the reals >1 merely take the previous lists and multiply them by any power of ten you choose! And to create the negative reals merely take all previous reals and multiply by minus 1!

(Course, performing the algorithm requires an uncountably infinite amount of RAM. Hope the manufacturers remembered to include that! ^_^)

Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

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

At what point in your calculation is the following number created: 1/3
Or how about pi - 3?

Your algorithm will create every terminating decimal, but when does it create a non-terminating one?

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

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

- The first thread creates a list of reals starting 0.1...
- The second thread creates a list of reals starting 0.2...
- ...
- The tenth thread creates a list of reals starting 0.0...
Then combine the results.

How?
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

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

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

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.

Perhaps, but I wonder if you can just do some countably infinite thing countably infinite times, and then do that countably infinite times etc... until you eventually (well, instantaneously in this case) build up something that is uncountably infinite. For example, could you (through an infinite sequence of infinite sequences of steps) construct the powerset of Z+? I would have thought that the reason we can't construct this normally is because there are infinite subsets of Z+ which would take an infinite amount of time to construct. But are those infinities an issue for this computer?

Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

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

Here's a consideration.
If you assume the Axiom of Choice, a countable union of countable sets is countable.
If you don't assume it, you don't know the cardinality of such a set.
So you can talk about doing something a countable number of times, but you don't solve anything.

As for the power set of N.
It is equivalent to the set of all functions from N to a two element set.

So, let's consider the set {0,1}.
We can consider a function from N to {0,1} to be represented by a binary string where each digit corresponds to the output of that digit's position.
i.e. the string 101 would correspond to the function that maps 1 to 1, 2 to 0, 3 to 1 and everything else to 0 (0 is not an element of N in this discourse, but it doesn't matter).

This thread has a method of building bit-strings
viewtopic.php?f=17&t=95774

At each stage, it can generate a finite number of finite bit-strings.
Yet it doesn't ever build an infinite string (and these exist) and so doesn't generate every bit-string.

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

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

At what point in your calculation is the following number created: 1/3

I thought it was pretty trivial to create that number assuming an infinitely fast computer:

Start at t=0 with "0."
Keep halving the interval and adding another "3"

You ask at what point is the string representing 1/3 created - I say at exactly t=1

lorb wrote:

- The first thread creates a list of reals starting 0.1...
- The second thread creates a list of reals starting 0.2...
- ...
- The tenth thread creates a list of reals starting 0.0...
Then combine the results.

How?

What do you mean how? How the f*ck have we built an infinitely fast computer anyhow? :p

Have the timing of each thread be such that they all finish by t=1 as per the above worked example. Then simply combine them all together at any point after t=1 using the same sort of recursive process - with all those infinite parallel threads finishing at, say, t=2.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

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

dudiobugtron wrote:Perhaps, but I wonder if you can just do some countably infinite thing countably infinite times, and then do that countably infinite times etc...

I'm not 100% sure I get what you're going after, but I think that "do countably infinite thing infinite times" needs to appear an uncountable number of times within that "etc.", otherwise you just have aleph_0 * aleph_0 = aleph_0 (or maybe aleph_0^3 = aleph_0.)

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

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

Xenomortis wrote:Here's a consideration.
If you assume the Axiom of Choice, a countable union of countable sets is countable.
If you don't assume it, you don't know the cardinality of such a set.
So you can talk about doing something a countable number of times, but you don't solve anything.

Thanks Xenomortis and EvanED. Yes that does answer my question about infinite lots of infinity exactly. It's kind of like how the finite union of finite sets is finite; you'd need an infinite union of finite sets to get an infinite set.
I guess I'll have to wait until we can get an uncountably infinite amount of parallel processors then, as jaap suggests.

-----

Going back to my question about random numbers, though, consider the following thought experiment:

Imagine we have a computer with infinite RAM, and the ability to generate sufficiently random real numbers between 0 and 1. By sufficiently random, I mean that every real number between 0 and 1 has a possibility of being generated. (I won't worry about how it generates this random number, but for the sake of argument assume it is possible!)

Now, what if we tell the computer to do this (excuse the horrible code):

Code: Select all

`10 Generate a random number20 goto 10`

And just set it going. Is there a real number between 0 and 1 that wouldn't be generated by this process?

PS: I think it only needs countably infinite RAM to hold any particular real number in RAM, is that true?

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

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

dudiobugtron wrote:And just set it going. Is there a real number between 0 and 1 that wouldn't be generated by this process?

It depends on how your "infinite computer" is defined. Most definitions, it's only going to generate a countable number of random numbers, so it's almost certain to not generate any particular real number you care to name.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

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

dudiobugtron wrote:I guess I'll have to wait until we can get an uncountably infinite amount of parallel processors then, as jaap suggests.

He he. The BlueGene/ℵ1. I want one.

Of course, as soon as you get the BlueGene/ℵ1 they'll announce the BlueGene/ℵ2 and yours will be obsolete...

Going back to my question about random numbers, though, consider the following thought experiment:

Imagine we have a computer with infinite RAM, and the ability to generate sufficiently random real numbers between 0 and 1. By sufficiently random, I mean that every real number between 0 and 1 has a possibility of being generated. (I won't worry about how it generates this random number, but for the sake of argument assume it is possible!)

Now, what if we tell the computer to do this (excuse the horrible code):

Code: Select all

`10 Generate a random number20 goto 10`

And just set it going. Is there a real number between 0 and 1 that wouldn't be generated by this process?

If you only have a processor that runs, uh, countably fast (whatever that means), or a countable number of such processors, then yes; even at the end of time (whatever that means) they'll still have only generated a countable number of numbers.

(To make that a little more precise, what I mean by "countably fast" is that in any finite amount of time, it only can run a countable number of those steps. What I mean by "at the end of time" is if the number of seconds is countable.)

PS: I think it only needs countably infinite RAM to hold any particular real number in RAM, is that true?

Yes

Kick
Posts: 112
Joined: Thu Nov 17, 2011 6:24 am UTC
Location: Pennsylvania
Contact:

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

Everything else I normally do, but with F@H running in the background all the time.
I'm never sarcastic.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

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

jaap wrote:All you need is some parallel processing. Uncountably infinitely many processes running in parallel, that is.

With uncountably infinite RAM, of course.
How do you address that sort of shit? I guess you could use Dedekind cuts or Cauchy sequences... OTOH, it's not going to be easy to get to the majority of RAM words, since they have uncomputable addresses. And the same applies to addressing the processors themselves.

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

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

elasto wrote:
lorb wrote:
- The first thread creates a list of reals starting 0.1...
- The second thread creates a list of reals starting 0.2...
- ...
- The tenth thread creates a list of reals starting 0.0...
Then combine the results.

How?

What do you mean how? How the f*ck have we built an infinitely fast computer anyhow? :p

Have the timing of each thread be such that they all finish by t=1 as per the above worked example. Then simply combine them all together at any point after t=1 using the same sort of recursive process - with all those infinite parallel threads finishing at, say, t=2.

Even if we suppose that the first thread actually succeeds in creating a _list_ of all reals starting with 0.1 it's no trivial task to combine it with a list of all reals starting with 0.2. You can't (trivially) append something at the end of an infinite list. Or maybe you can give an algorithm that does what you propose? So that we can see what the "lists" you are talking about actually look like. Or maybe just tell me: what are the first 3 reals on the list that is the endresult?
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

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

On the upside, if you did manage it, you've just well-ordered the reals!

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

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

Actually you can trivially append something at the end of an infinite list. For example, you could use a semi-colon after the '...'.

I think it's the idea of using '...' to mean 'and the rest of the reals' which is a bit spurious.

(PS: eg, if I want to write a 'list' which first contains all of the even positive integers, then all of the odd ones, I might write it:
2, 4, 6, 8, ... ; 1, 3, 5, 7, ...
)

Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

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

That's a question of notation, but it leaves the question of computation unanswered.

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

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

Xenomortis wrote:That's a question of notation, but it leaves the question of computation unanswered.

I was imagining something like this:
----
If there exists an n in {n | we haven't yet generated the nth real number starting with 0.1...}, then choose the lowest such n.
Generate the nth real number starting with 0.1 .
Repeat.

Otherwise, if there exists an n in {n | we haven't yet generated the nth real number starting with 0.2...}, then choose the lowest such n.
Generate the nth real number starting with 0.2 .
etc....
-----

Obviously this won't generate all the of the real numbers, since they are not countable (nor, as you said, well-ordered). But my point was that their unaccountability was the problem, not the impossibility of computing something after you've already computed infinite other things.

________________________________
---------------------------------------------

As a separate point, I wonder if we can utilise the hypernaturals (since |*N| = |R| ) to visualise some sort of uncountably infinite computer* which maintains a pseudo-iterative structure. Could we construct some analogue of 'steps' or algorithms which work well with the transfer principle?

*(EDIT: I was tempted to call this a 'hypercomputer', but then discovered that this term is already used to discuss the exact sort of thing we're wondering about already: http://en.wikipedia.org/wiki/Hypercomputation !

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

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

Newcomers to this thread may not be aware that it inspired a "spinoff" thread a couple of years ago: "The set of all computable reals & diagonalization" aka "Properties and models of infinitely fast computation"
http://forums.xkcd.com/viewtopic.php?f=12&t=58941
I vaguely remember another good thread discussing transfinite computation; but maybe I'm just imagining things.

jareds
Posts: 436
Joined: Wed Jan 03, 2007 3:56 pm UTC

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

Just to summarize a bit of information from that spin-off, we spent a lot of time discussing a well-defined model of transfinite computing that was not really uncountable computing. (The model allowed for running any transfinite ordinal number of steps, but it would provably either halt or get into a repeating loop within a countable number of steps. If this doesn't make sense, imagine running a Zeno machine to completion an infinite number of times in succession. You could number the steps with ordinals less than ω2, which is still countable. This model extended on that.)

I think one of the big problems one would have with a model of computation that operates in uncountable realms is that traditional models of computation use programs that can be represented as finite strings, so the number of programs is countably infinite. Thus, for example, almost all the reals will be uncomputable, if "computable real" means "there exists a program that computes that real (and only that real) on empty input", and uncountably infinite storage or speed don't help: you need uncountably many programs.

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

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

Thanks! That thread made pretty interesting reading. Although a lot of the terminology was a bit advanced for me, it did give me a pretty good idea of the discussion and thought that has already gone into the topic.

I'm still having trouble convincing myself that you can't construct all of the reals computationally on this infinite computer, when it's so easy to construct them mathematically. I guess I'll have to be content with believing that you can't, though.

WanderingLinguist
Posts: 237
Joined: Tue May 22, 2012 5:14 pm UTC
Location: Seoul
Contact:

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

dudiobugtron wrote:...when it's so easy to construct them mathematically.

Is it, though? All of them, I mean.

If you had an infinitely fast immortal person, could that person construct all the reals? What algorithm could you use (mathematically) that would cover all the reals given an infinite amount of time?

I don't think it's so easy to construct them mathematically as you think it is...

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

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

What algorithm could you use (mathematically) that would cover all the reals given an infinite amount of time?

An uncountably infinite amount of time?

As it happens, though, I was using the word 'construct' in a different sense. Here are some ways you can construct the reals mathematically:
http://en.wikipedia.org/wiki/Constructi ... al_numbers
I think my use of the word 'construct' in this sense is valid. If you like, however, replace my earlier sentence with this one:
I'm still having trouble convincing myself that you can't generate all of the reals algorithmically on this infinite computer, when it's so easy to define them theoretically.

PS: Of course, I only think it is easy because people much smarter than myself have shown us how to do it....

Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

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

WanderingLinguist wrote:If you had an infinitely fast immortal person, could that person construct all the reals? What algorithm could you use (mathematically) that would cover all the reals given an infinite amount of time?

I don't think it's so easy to construct them mathematically as you think it is...

"Construction" has a different meaning in a mathematical context and isn't relevant here.
However, the set R = {r⊂Q | r defines (or is) a Dedekind cut of Q} is well defined and is bounded by P(Q). This set exists and we can talk about it.

WanderingLinguist
Posts: 237
Joined: Tue May 22, 2012 5:14 pm UTC
Location: Seoul
Contact:

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

Ah, I got it now. Yay, terminology.

Posts: 15
Joined: Sun Oct 14, 2012 9:28 pm UTC

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

An infinitely fast computer would do wonders for formal verification of software. You could just enumerate the entire state space of most real programs (given that the space is bounded of course but that is usually the case in real software) and look for deviations from the specification. Then software development will actually deserve to be called engineering.

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

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

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"

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

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

Already discussed earlier in the thread. You probably want to be careful with Solomonoff induction, because it arguably creates every possible universe, including hellscapes filled with unimaginable numbers of suffering sentient minds. If you believe that simulated sentience is still sentience (which you should), then that's probably grossly unethical.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tac-Tics
Posts: 536
Joined: Thu Sep 13, 2007 7:58 pm UTC

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

I would use it to prove that it isn't infinitely fast.

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

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

Tac-Tics wrote:I would use it to prove that it isn't infinitely fast.

How?

Tac-Tics
Posts: 536
Joined: Thu Sep 13, 2007 7:58 pm UTC

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

dudiobugtron wrote:
Tac-Tics wrote:I would use it to prove that it isn't infinitely fast.

How?

There are lots of ways to create paradoxes. If there are components moving infinitely fast inside the computer, you can show relativity is violated. You can also use it to solve the halting problem.

In either of those cases, you end up with a contradiction. And by principle of explosion, I can prove the computer isn't infinitely fast.

Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

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

Except, not.

Solving the halting problem on a weaker class of computers (like finite speed computers) is not a paradox.

There are many models of infinitely fast computers that are perfectly sound, mathematically.
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.

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

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

Showing a relativity violation isn't contradictory. It means relativity is wrong, but that's how science normally works.

Showing that you can solve the halting problem isn't contradictory. The halting problem applies to Turing Machines, which an infinitely fast computer is not. It's definitely possible for an infinitely fast machine (for several definitions of "infinitely fast" to solve the halting problem for TMs, though there is another halting problem for the more powerful machines that it can't solve.

Even if you could derive a contradiction, this is physical reality, not logic. That just shows that physical reality is inconsistent, or more likely, that your model of physical reality is inconsistent, and you need to get a better one. It doesn't go back and undo one of the premises to maintain validity.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tac-Tics
Posts: 536
Joined: Thu Sep 13, 2007 7:58 pm UTC

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

Even if you could derive a contradiction, this is physical reality, not logic. That just shows that physical reality is inconsistent, or more likely, that your model of physical reality is inconsistent, and you need to get a better one. It doesn't go back and undo one of the premises to maintain validity.

These kinds of arguments are why philosophers go unemployed. If you are so uncertain of your own foundations that you can't take modern relativity as an axiom, you won't find the foothold to make any useful statements at all. Any post could simply be retorted with "well, maybe everything we know is wrong."

Science didn't get to where it is today through continuous self-doubt. The majority of bad theories weren't totally invalid. Most had the right idea, but the wrong formula, or it was something that worked in similar situations, but didn't work here, or it was mostly right, but needed some twerking.

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

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

Uh, what? Modern relativity almost certainly *is* wrong, which is why quantum gravity is hard. Science *is* about constant self-doubt, because we've been wrong about everything, and likely will never stop being wrong. Of course, our degree of wrongness goes down over time, but still, we're always wrong, about everything, and always will be. That's what science is about. There are no axioms. Anything might be proven wrong.

Your post was just wrong. You can't use an infinite computer to prove infinite computers can't exist. That's just silly. You could try and use a *theoretical* computer to do so, because then you're working in logic where you can assume an impossible thing, but if an infinitely fast computer actually exists, it actually exists.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

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

What you could probably do is have it spit out a sufficiently compelling compelling argument that people would accept as proof that it isn't infinitely fast. Or better yet, that the computer doesn't exist at all and you've never heard this argument.

For added sophistic fun: Consider that there is no way to know your cat isn't such a computer.
The thing about recursion problems is that they tend to contain other recursion problems.

Posts: 165
Joined: Sat Feb 13, 2010 11:25 pm UTC

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

Quizatzhaderac wrote:What you could probably do is have it spit out a sufficiently compelling compelling argument that people would accept as proof that it isn't infinitely fast. Or better yet, that the computer doesn't exist at all and you've never heard this argument.

For added sophistic fun: Consider that there is no way to know your cat isn't such a computer.

I do not have a cat.
I found my old forum signature to be awkward, so I'm changing it to this until I pick a better one.

Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

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

Then you should be sad, because you don't have something that may be an infinitely fast computer in disguise.
I know I am.

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

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

Quizatzhaderac wrote:What you could probably do is have it spit out a sufficiently compelling compelling argument that people would accept as proof that it isn't infinitely fast. Or better yet, that the computer doesn't exist at all and you've never heard this argument.

For added sophistic fun: Consider that there is no way to know your cat isn't such a computer.

But cats halt and their output is countable?

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

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

Hmmm.... Well let's split cats into two categories.
1) The regular kind
2) The infinite computer kind, that convinces people that is doesn't exist.

We can then split people into two categorize or three sub categories.
1. People who believe they have cats
2. People who don't believe they have cats
1. Because they don't actually have a cat.
2. Because they have an infinite cat that convinced them they don't have a cat.
So if you don't believe you have a cat, that's actually evidence that you have an infinite cat.
The thing about recursion problems is that they tend to contain other recursion problems.