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

User avatar
kernelpanic
Posts: 891
Joined: Tue Oct 28, 2008 1:26 am UTC
Location: 1.6180339x10^18 attoparsecs from Earth

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

Postby kernelpanic » Mon Aug 17, 2009 1:56 am UTC

munchman wrote:I'd attempt to run Vista
You'd fail.
Vista wrote:What drivers have you got? Signed? Wait! Are you sure you want to run this program? Are you sure? Your antivirus software is out of date! And so on...
I'm not disorganized. My room has a high entropy.
Bhelliom wrote:Don't forget that the cat probably knows EXACTLY what it is doing is is most likely just screwing with you. You know, for CAT SCIENCE!

Image

lightvector
Posts: 222
Joined: Tue Jun 17, 2008 11:04 pm UTC

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

Postby lightvector » Wed Aug 19, 2009 10:02 am UTC

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.

User avatar
Earlz
Gets Obvious Implications
Posts: 785
Joined: Sat Jun 09, 2007 8:38 am UTC
Location: USA
Contact:

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

Postby Earlz » Sun Aug 23, 2009 1:48 am UTC

I would make a infinite-bit number represent a configuration of a universe and then I would loop through each number and then check that number using an alogorithm to check if that universe configuration is exactly equivalent to ours. Then I would see what I will be doing in the next few years and enjoy watching an infinite loop of feedback at the "now" while I'm watching the computer watch me watching the computer..... Then, I would prove to you that indeed, I was with your mother.
My new blag(WIP, so yes it's still ugly..)
DEFIANCE!
Image
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD

User avatar
Midnight
Posts: 2170
Joined: Mon Dec 10, 2007 3:53 am UTC
Location: Twixt hither and thither. Ergo, Jupiter.

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

Postby Midnight » Tue Aug 25, 2009 6:08 am UTC

Probably cure cancer. If possible, code this thing to be self-evolving but instill in it a certain benevolence so as it evolves, it aims to cure the maladies of mankind. Of course, then it might try to like, create a disease to wipe away humanity, like all the AIs in all the cheap movies.

No, wait. Make 2 AIs, and ONE of them is a self-evolving version that could be hardwired to do whatever I say and love me and think I'm the coolest thing ever and have my interests at heart. Use THAT one to keep the disease-curing one in check.

or something like that--making a couple of self evolving ones that alone do not have the power to destroy humanity, and are pitted against each other.
uhhhh fuck.

H2SO4
NOCTUNICUS, LORD OF SLEEP
Posts: 931
Joined: Thu Nov 09, 2006 6:36 am UTC

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

Postby H2SO4 » Tue Aug 25, 2009 7:13 am UTC

Snipe people on eBay with a 100% success rate just because I can.
But I, being poor, have only my dreams. I have spread my dreams under your feet; tread softly, because you tread on my dreams.

EclipseEnigma
Posts: 30
Joined: Wed Jul 15, 2009 1:17 am UTC

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

Postby EclipseEnigma » Thu Aug 27, 2009 12:10 pm UTC

I would solve every Project Euler (link: http://projecteuler.net/) at the same time

User avatar
minno
Posts: 152
Joined: Fri Jul 31, 2009 11:33 pm UTC
Location: Where you least expect it.

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

Postby minno » Fri Sep 04, 2009 1:54 am UTC

Chances are that someone else decided to say this, but it's still my pick:

Code: Select all

while 1: pass


Infinite speed vs. infinite loop...
If you fight fire with fire, you'll get twice as burned.

Sunshineq
Posts: 1
Joined: Fri Sep 04, 2009 4:44 am UTC

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

Postby Sunshineq » Fri Sep 04, 2009 4:49 am UTC

Ended wrote:This.



This post is old now, but I made an account to comment on it anyways. I came up with a story eerily similar to this one. (Infinitely fast computer, simulated universe, scientists discovering they were simulated). Except in mine, one of the characters killed themselves.

User avatar
Earlz
Gets Obvious Implications
Posts: 785
Joined: Sat Jun 09, 2007 8:38 am UTC
Location: USA
Contact:

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

Postby Earlz » Sat Sep 05, 2009 5:56 am UTC

Sunshineq wrote:
Ended wrote:This.



This post is old now, but I made an account to comment on it anyways. I came up with a story eerily similar to this one. (Infinitely fast computer, simulated universe, scientists discovering they were simulated). Except in mine, one of the characters killed themselves.


hmm.. first post and you can post links? strange.. course it is quoted.
My new blag(WIP, so yes it's still ugly..)
DEFIANCE!
Image
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD

User avatar
'; DROP DATABASE;--
Posts: 3284
Joined: Thu Nov 22, 2007 9:38 am UTC
Location: Midwest Alberta, where it's STILL snowy
Contact:

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

Postby '; DROP DATABASE;-- » Fri Sep 11, 2009 5:43 am UTC

I'm pretty sure the "no links before 5 posts" rule was never software-enforced. Mods just de-link them. There are cases where the link is obviously relevant and allowed to stay.
Midnight wrote:Probably cure cancer. If possible, code this thing to be self-evolving but instill in it a certain benevolence so as it evolves, it aims to cure the maladies of mankind. Of course, then it might try to like, create a disease to wipe away humanity, like all the AIs in all the cheap movies.

No, wait. Make 2 AIs, and ONE of them is a self-evolving version that could be hardwired to do whatever I say and love me and think I'm the coolest thing ever and have my interests at heart. Use THAT one to keep the disease-curing one in check.

or something like that--making a couple of self evolving ones that alone do not have the power to destroy humanity, and are pitted against each other.
Think about what infinite processing speed means... you could write programs by brute-forcing code (in any language, even) and testing all possible inputs to ensure the output is what you want. So in literally no time, you'd have created a completely benevolent AI.

Other fun ideas include perfectly realistic 3D renderings of anything and everything, brute-forcing a program that can tell how awesome a song is and then brute-forcing music to create the perfect song, even creating an SVG renderer that doesn't take bloody ages to render images that use a lot of blur. Similarly, you could feed it a sound, image, video, copy of a game, really anything and have it make any change you want. Scan in a photo and have it rotate the subject 180 degrees. You could do this just by trying every possible change, but I'm not sure how it'd know when it got the right one...

Then you have it figure out how to create the hardware to interface yourself with a totally kickass VR program, and do so. Maybe even provide it with movable arms of some sort so it can build the hardware itself (only once you're certain it's not going to stab you to death, or try to move so fast it catches fire, etc). You'd have the ultimate video game, indistinguishable from reality. I mean brute-force hardware design on this thing means being able to design anything that can exist, simulate it in every possible scenario in a perfect simulation, and then you'd only need to figure out how to go about building the damn thing - and it could help you build the tools to do so, in a bootstrapping process, giving you a design to build more complex tools out of what you have, etc. You'd probably end up with some sort of device you can swallow or stick on your head, that takes completely over your nervous system with no side effects and no possibility of malfunction - after all, it's been tested in literally every possible scenario.

Then you feed it pics and info about your favourite characters *glances at avatar* and create them in the VR world as well... oh come on don't tell me you didn't think it already. >_> Alternatively, use your new ridiculously awesome tools to create perfectly realistic robots, in any form you want.

tl;dr: I'd have it brute-force design and test some ridiculously cool shit, including perfect VR, and get bloody rich off it.
poxic wrote:You suck. And simultaneously rock. I think you've invented a new state of being.

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

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

Postby userxp » Fri Sep 11, 2009 10:00 am UTC

'; DROP DATABASE;-- wrote:Think about what infinite processing speed means... you could write programs by brute-forcing code (in any language, even) and testing all possible inputs to ensure the output is what you want. So in literally no time, you'd have created a completely benevolent AI.

I don't think it is possible to brute-force software.
If you tried, for example, every possible program smaller than 5MB in size, gave each program a photo as input, and filtered only the programs that returned the modified photo, you would probably end with billions of programs that do it. However, out of these of programs 99.9% would just return garbage if you put another photo. And even if you found a program that works with 10000 different photos, you couldn't be sure that it would work the 10001st time.

Similarly for all these cure cancer, make an AI, simulate the universe, break the internet: you still have to code it.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

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

Postby Berengal » Fri Sep 11, 2009 3:01 pm UTC

I've been thinking that the whole time. Brute-forcing isn't hard nor interesting; just enumerate all programs. The problem is that this gives you *all* programs. You also need a program that takes a program as input and tells you if it's a good program or not. Could you write this?

Brainfuck has 8 symbols. Given a program no longer than 1000 characters, guaranteed to be valid (no unmatched brackets), can you write a program that determines if it does something useful, say, calculate factorials, primes, or if given a decimal number input, outputs that many elements of the fibonacci series? It might be possible on a regular machine, but you might also run into the halting problem. Given a halting oracle and the ability to exhaustively test all inputs, tools I assume an infinitely fast computer has, testing for such programs shouldn't be too hard, but what about programs that make cool images?

How about just testing images themselves, a requirement for a program testing programs that produce them? Given an infinitely fast computer, could you write a program that determines if an image is cool or not? If you do, do you really need the infinitely fast machine to do this, or could you do it on a regular machine as well? How about just writing a program that produces cool pictures in the first place, on a regular computer? I've done this, and the images were done in a few minutes at most, running in the python interpreter, in a single thread on a regular 3GHz CPU with regular, finite 4GB RAM.

An infinitely fast computer can enumerate all programs, which makes it theoretically possible to simply find a program that does what you want, but simply enumerating programs isn't enough. You also need a program that selects the program you want, or you're stuck doing it by hand. My guess it's easier to just write the program in the first place rather than write the program that finds the program you want.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
'; DROP DATABASE;--
Posts: 3284
Joined: Thu Nov 22, 2007 9:38 am UTC
Location: Midwest Alberta, where it's STILL snowy
Contact:

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

Postby '; DROP DATABASE;-- » Fri Sep 11, 2009 10:22 pm UTC

Well, consider that you can test all possible inputs to each program. The only question is how you know if a given output matches what it should be for a given input.
poxic wrote:You suck. And simultaneously rock. I think you've invented a new state of being.

User avatar
Squid Tamer
Posts: 220
Joined: Fri Apr 03, 2009 3:59 am UTC
Location: Over there
Contact:

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

Postby Squid Tamer » Sat Sep 12, 2009 1:12 am UTC

WARNING: Rambling that you probably already know.

And for any randomly generated program selection (On an infinite computer), you have an infinite number of programs that do what you want, an infinite number that don't, and an infinite number that appear to do what you want, but don't.

Getting rid of the second group is easy, but separating the first and the second would be harder. Let's assume that we're looking for the correct output for any given input.

Let's pretend that the input is:

Code: Select all

What is 8+4?
What is the capital of Russia?
What time is it?


Program 1 outputs:

Code: Select all

1121.11212.11

You can throw that one out, it isn't useful for this.

Program 2 outputs:

Code: Select all

12
Moscow
5:45 P.M.


Program 3 Also outputs that same thing. But here are the actual source codes of the two:
Spoiler:
Program 1:

Code: Select all

(Super Duper AI


Program 2:

Code: Select all

print "12"
print "Moscow"
print "5:45 P.M."
if $iouoiureowuouo == $lfdsajooooaab:
print "print aldkjdlfjuew898fd8s7987ggdsfdsfafdsajgkjg-4-89jlj9440-2 4 jgsdljdsfl87a83fdslj00...


See, there are going to be a lot like that... (Trails off, having written an overly long thing that is pretty easy to explain in one sentence.)

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

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

Postby phlip » Sat Sep 12, 2009 3:50 am UTC

As I see it, it's similar to the P=NP thing...

Handwavily, let C be the class of all problems where it's easy to write a correct program to solve it, without regards for efficiency or anything (it's an infinite-speed computer, after all). And let NC be the class of all programs where it's easy to write a correct problem that'll take an input and an output, and verify that the output is correct. Obviously these definitions depend on your level of laziness and definition of "easy", but still.

Given a sufficiently large infinity, given a program in NC, it's simple enough to take a verifier, and brute-force a solver. In particular, for the obvious brute-forcing method, you need the infinity to be high enough to run through countably-infinitely many countably-infinite loops:

Code: Select all

def valid(input, output):
  # code here

solver = None
for prog in all_programs:
  valid_solver = True
  for input in all_inputs:
    output = prog(input)
    if not valid(input, output):
      valid_solver = False
      break
  if valid_solver:
    solver = prog
    break
This might be able to be rearranged with some kind of interleaving to have just one coutable-infinite loop... but I'm too lazy to do so.

So, for a computer that could run that algorithm, C = NC.

However, strong AI isn't really in NC either.

Code: Select all

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

User avatar
Giant Speck
Bouncy Sex Marshmallow
Posts: 3797
Joined: Tue Sep 08, 2009 12:30 pm UTC
Location: Tucson, Arizona

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

Postby Giant Speck » Sun Sep 13, 2009 2:21 pm UTC

I'd lock myself in a bomb shelter and hope to God that the computer never becomes self-aware.
"Did I say recently that I love Giant Speck? Because I love Giant Speck. He is the best." - Weeks

User avatar
el_loco_avs
Posts: 1294
Joined: Wed Feb 06, 2008 1:14 pm UTC

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

Postby el_loco_avs » Tue Sep 15, 2009 12:06 pm UTC

I'd clog up the internets.
You go your way.
I'll go your way too.

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

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

Postby Agent_Irons » Sun Sep 27, 2009 6:46 am UTC

See, what you can do with an infinitely fast computer (say, for the sake of argument, it's not that infinite. It takes two seconds to run infinitely many steps.) is arbitrarily improve any algorithm. Any algorithm you know to be correct (for example factoring primes) you simply test against all programs less than a certain size. Find the one with the shortest running time that produces the same output as the slow algorithm across all possible inputs. You may want to look at those that are close to the shortest, in case the shortest one uses mathematics that haven't been invented yet.

That's the real value of an infinitely fast computer. It still doesn't prove P = NP, (finite program size) but it's still pretty nice.

EduardoLeon
Posts: 111
Joined: Wed Sep 30, 2009 2:26 am UTC
Location: Lima, Perú
Contact:

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

Postby EduardoLeon » Fri Oct 02, 2009 3:27 pm UTC

It depends on the Turing degree of the infinitely fast computer I would have.

Meteorswarm wrote:But who *cares* about algorithm efficiency? You can solve any problem instantly once you have any solution written, so why bother with quick solutions?


Of course, you wouldn't care about the efficiency of algorithms that solve problems that can be solved with Turing machines. But you would care about those algorithms that perform substantially more computation than can be done with Turing machines, in particular, algorithms that solve problems that can't be solved with Turing machines, but can be solved with the particular type of machine you would have.
Gott weiß ich will kein Engel sein!

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

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

Postby Agent_Irons » Fri Oct 02, 2009 4:24 pm UTC

Meteorswarm wrote:
Agent_Irons wrote:See, what you can do with an infinitely fast computer (say, for the sake of argument, it's not that infinite. It takes two seconds to run infinitely many steps.) is arbitrarily improve any algorithm. Any algorithm you know to be correct (for example factoring primes) you simply test against all programs less than a certain size. Find the one with the shortest running time that produces the same output as the slow algorithm across all possible inputs. You may want to look at those that are close to the shortest, in case the shortest one uses mathematics that haven't been invented yet.

That's the real value of an infinitely fast computer. It still doesn't prove P = NP, (finite program size) but it's still pretty nice.


But who *cares* about algorithm efficiency? You can solve any problem instantly once you have any solution written, so why bother with quick solutions?

Folding@Home, for one. Bandwidth means you can't solve it for them instantly, but you can at least accelerate the process significantly.

More interestingly, which language would you code for the infinitely fast machine in?

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

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

Postby Berengal » Fri Oct 02, 2009 4:45 pm UTC

Agent_Irons wrote:Folding@Home, for one. Bandwidth means you can't solve it for them instantly, but you can at least accelerate the process significantly.
I have a feeling solving the bandwidth problem for Folding@Home involves a truck and large amounts of tape. For some of the other distributed projects, a programmer capable of writing a program enumerating all possible inputs is probably even faster.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Poohblah
Posts: 53
Joined: Thu Feb 26, 2009 3:54 am UTC

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

Postby Poohblah » Sat Oct 03, 2009 1:02 am UTC

Solve chess

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

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

Postby TheChewanater » Sat Oct 03, 2009 3:32 am UTC

Write a program that brute forces all the possible commands that can be performed by an infinitely fast computer, and then decides which would be the coolest thing to do based on an algorithm generated by brute-forcing all the possible programs that can be made. Of course, this would need another program to generate, which would take an infinite amount of time to write even on an infinitely fast computer. Unless there is another program generating that one...

Oh, and once it's done it posts what it did in this topic.
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
Brooklynxman
Because I'm Awesome
Posts: 609
Joined: Tue Jan 20, 2009 4:27 pm UTC
Location: Here
Contact:

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

Postby Brooklynxman » Sat Oct 03, 2009 4:50 am UTC

_MC_ wrote:I would play Duke Nukem Forever


I was reading this thread waiting for someone to mention just play games.

The timmy-god story is......interesting.

EDIT: Upon thinking: Why create a clone of this universe (although I may do it for lotto numbers) when you can create your own playground. Do WHATEVER you want.

Of course, eventually, anyone in that position would eventually become a benevolant god, as you realize these aren't mere simulations but for all intents and purposes are real people....real life.
We figure out what all this means, then do something large and violent

The thing about changing the world...once you do it the world's all different.

I'm Angel. I beat the bad guys.

Spoiler:
Image

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

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

Postby MHD » Mon Oct 05, 2009 7:30 pm UTC

Poohblah wrote:Solve chess


This would actually be possible, making a tree structure of all possible move patterns and then making an unbeatable chess program, that simply chose a path down the tree to victory.
Assuming that for the first single turn of two players both have 20 possible moves... >.< ow, that's a lot of data. But it'd work.

Also any other finite state game would be solveable like this.
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"

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

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

Postby Notch » Tue Oct 06, 2009 12:19 pm UTC

Since all computers are finite state machines, a game of Quake is a finite state game as well.. Ignoring network latency, as that adds a random element to the game.

Solving quake deathmatch would be fun. Once the player makes a mistake, the computer can prove it'll never lose. :D

pavja2
Posts: 29
Joined: Mon Oct 05, 2009 9:31 pm UTC

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

Postby pavja2 » Tue Oct 06, 2009 10:40 pm UTC

See if it is really my cheap PC that makes Vista fail...

Then go ahead and use it to create a new internets with no tubes...

Poohblah
Posts: 53
Joined: Thu Feb 26, 2009 3:54 am UTC

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

Postby Poohblah » Wed Oct 07, 2009 5:23 pm UTC

MHD wrote:
Poohblah wrote:Solve chess


This would actually be possible, making a tree structure of all possible move patterns and then making an unbeatable chess program, that simply chose a path down the tree to victory.
Assuming that for the first single turn of two players both have 20 possible moves... >.< ow, that's a lot of data. But it'd work.

Also any other finite state game would be solveable like this.


A small chunk of the data can be removed when the computer realizes that there are many paths to end up at certain positions, especially in the opening, when it is really easy to transpose from one opening line to another.

The solving algorithm doesn't need to be completely brute force for chess, because there are certain positions that are won and so the computer doesn't need to calculate all possibilities at that point.For example, queen and king vs. king and no other pieces on the board.

But yes, a ton of data, certainly.

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

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

Postby Yakk » Wed Oct 07, 2009 6:57 pm UTC

Naw -- you have infinite computing power. Why bother using lots of memory?

Generate a canonical ordering on moves. Maintain a list of moves (say 1 million deep), and presume that any game that neither can win after 1 million moves is a stalemate branch (at least effectively).

Do an alpha-beta search, where you keep track at each node the last move checked and the victory result of the move. Simply iterate over all legal moves on each branch.

Your position value function is simply 0 for a tie, 1 for a victory, and -1 for a loss.

Viola: an O(1 million) memory algorithm that takes a large (if finite) period of time that will solve chess, presuming that there are no 1 million + round games of chess that are both optimal and not a stalemate.
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.

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

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

Postby phlip » Wed Oct 07, 2009 11:11 pm UTC

Yakk wrote:presume that any game that neither can win after 1 million moves is a stalemate branch (at least effectively).

With things like the 50-move rule and threefold repetition, Chess is a finite game... so, naturally, it can be solved in O(1) time and space. Just with a rather large constant term.

Indeed, with the 50 move rule, we can make a very loose upper bound... there are 16 pawns, each of which can move at most 6 times, and 30 pieces that can be captured... a total of 126 events that can reset that 50 move counter. Now, you can't have all of those in a single game... for each pair of pawns, either one will have to make a capture (thus having both a capture and a pawn move at the same time), or one pawn will have to be captured before making it to the end of the board... but still, let's call it 126 as a loose upper bound.
So, 126 times, we can have just under 50 moves each, followed by one move by one player that'll reset the counter (for the upper bound, say that this is the 50th move, by the second player). Then another 50 moves to get to the draw. So 6350 moves each.

Well short of a million.

Code: Select all

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

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

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

Postby headprogrammingczar » Thu Oct 08, 2009 12:18 am UTC

I forgot about the fifty move rule. Good find. With proper culling, you definitely have enough memory on a commercial hard drive to solve chess.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

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

Postby Agent_Irons » Thu Oct 08, 2009 8:17 am UTC

headprogrammingczar wrote:I forgot about the fifty move rule. Good find. With proper culling, you definitely have enough memory on a commercial hard drive to solve chess.

There are only 12 pieces that can go into a single square. King, queen, bishop, knight, rook, pawn, in both white and black. So: 64 squares * 4 bits ~= 30 bytes, absolute maximum. Using a clever delta compression from some commonly found board positions could make that much smaller. 30 bytes *7000 board moves is 210kilobytes/game. The longest decisive chess games end in hundred-move endgames but top out at about 250 moves. So a more realistic estimate is about 7k a game. The optimal tree is of course larger, but I don't even know how to calculate how big it is. I suspect it's bigger at the top, and looks like a jellyfish.

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

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

Postby Yakk » Thu Oct 08, 2009 1:25 pm UTC

phlip wrote:
Yakk wrote:presume that any game that neither can win after 1 million moves is a stalemate branch (at least effectively).

With things like the 50-move rule and threefold repetition, Chess is a finite game... so, naturally, it can be solved in O(1) time and space. Just with a rather large constant term.

However, in the meta-rules of chess, if someone found a more than fifty sequence of no-pawn no-capture moves that still ended in one side or the other winning, the move count would be increased.

... bah, I'm out of date:
During part of the 20th century, with the discovery that certain endgames can only be won in more than fifty moves (without a capture or a pawn move) from certain positions (see History section), the rule was changed to include certain exceptions in which one hundred moves were allowed with particular material combinations. However, in 1992 FIDE abolished all such exceptions and reinstated the strict fifty-move rule.
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.

User avatar
Area Man
Posts: 256
Joined: Thu Dec 25, 2008 8:08 pm UTC
Location: Local

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

Postby Area Man » Thu Oct 08, 2009 6:08 pm UTC

Solve chess? Too easy for an IFC. I'd solve go on every size and shape board, including spherical and hyper-dimensional.
Bisquick boxes are a dead medium.

Muffinman42
Posts: 24
Joined: Wed Sep 23, 2009 7:33 pm UTC

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

Postby Muffinman42 » Tue Oct 13, 2009 4:50 pm UTC

Find the answer to life the universe and everything, just to see if 42 is right.
Then maybe simulate a whole universe and then Find prime numbers for money.
I would then buy the best internet connection possible, and just do as i feel, maybe make a super AI to test the "brain in a jar" logic puzzle, or play tetris, or i would just do what i normally do.

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

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

Postby userxp » Tue Oct 13, 2009 5:41 pm UTC

Serious answer: I would find money somehow, buy/construct a fortification in a desert island with an Internet connection, and hide there. Make a security system programmed to detonate the computer if anyone enters the island. Then sell computing time to anyone interested. After I have enough money, donate the computer to the science to investigate how it works.

turingmachinesarehot
Posts: 31
Joined: Thu Jan 17, 2008 6:32 pm UTC

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

Postby turingmachinesarehot » Wed Oct 21, 2009 11:18 am UTC

Naurgul wrote:I would brute-force NP-hard problems (and problems from even harder complexity classes) like there's no tomorrow.


Exactly my thinking. :D

EduardoLeon
Posts: 111
Joined: Wed Sep 30, 2009 2:26 am UTC
Location: Lima, Perú
Contact:

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

Postby EduardoLeon » Fri Oct 23, 2009 3:48 pm UTC

I would have to masturbate infinitely fast to infinitely fast porn.
Gott weiß ich will kein Engel sein!

User avatar
yavinfour
Posts: 14
Joined: Fri Apr 03, 2009 10:20 pm UTC
Location: PHILlIP-of-the-PINES
Contact:

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

Postby yavinfour » Fri Oct 23, 2009 7:42 pm UTC

Hey how about making a nice full-length CGI film in less than a week using that infinitely fast computer.
Image

EduardoLeon
Posts: 111
Joined: Wed Sep 30, 2009 2:26 am UTC
Location: Lima, Perú
Contact:

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

Postby EduardoLeon » Fri Oct 23, 2009 8:06 pm UTC

I would crack all security codez in zero time, since I would be able to factor products of arbitrarily high prime numbers.

If I also had an infinitely fast internet connection, I'd flood the net with trash data in no known protocol formal.
Gott weiß ich will kein Engel sein!


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests