49
$\begingroup$

Let's say that somehow, Earth suddenly acquired a computer with ridiculous speed. This computer can run a program described in a language of your choice, which can be described by a readme file that comes with the device. This device can have the capability to generate true random numbers, and run any program instantly (or nearly instantly, like 1 nanosecond, this does not matter because the input and output is bounded by USB protocol speed).

What would be the implications of said device, and what would it be used for? I imagine some extreme Monte Carlo simulations could be run on it, and many other things, but how would that impact society in the near future?

You cannot take apart or examine the machine in any way, it is a mysterious cubic meter of handwavium with a USB port where you drop in a file like input.txt and then pull out a file output.txt with normal USB protocol. (Yes this is sort of a limit on program size, but hey its an instant computer, what more can you expect?)

This cube computer can be plugged into one of our computers via USB, and it looks just like a USB flash drive to the computer. But as soon as you drop in a file named input.txt it will be read, deleted and an output.txt will be created or overwritten. It does not need a power supply either.

The program cannot be used to gather information about the architecture, system, or inner workings of the computer. This is not an actual computer with conventional circuits, and it is not bounded by the speed of light etc.

If this device is unique and it is found by, say, NASA, what advances would we see in the near future?

Improve this question
$\endgroup$
1

14 Answers 14

Reset to default
33
$\begingroup$

This is actually very interesting Mathematically (mathematics here means computer science, and computer science is NOT programming - it's a branch of pure, not applied, mathematics).

NOT the Halting Problem

First, let's get something out of the way - the halting problem. Most of the answers here give a wrong description of the halting problem. The halting problem is not that some programs never halts (indeed you can write a trivial infinite loop as an example of a program that never halts). The halting problem is a thought experiment about designing a universal non-halting program detector. The non-intuitive result of the thought experiment is that it's impossible to design a universal (works 100% of the time) non-halting program detection program.

A better defined scenario

Now, let's restate the scenario - the computer is able to execute any program that don't have infinite loops in constant (or nearly constant) time.

Interestingly, this result is very powerful regardless if it takes the computer 1ns to run any program or 1 hour to run any program or even 1 day to run any program - it would still be a major breakthrough in computing. The actual execution speed of the computer is not as interesting as the fact that it can run any program in a predictable amount of time.

The breakthrough

So what's the breakthrough here?

You've basically just proven that P = NP.

Let me emphasize that:

You've just proven that P = NP.

and this is BIG.

Implications

The first practical implication of this is that all recursive formulas are now trivially calculable in constant time. One of the most mind blowing effect of this is that we can now easily generate and test for prime numbers. Imagine being able to just call up the 2543rd prime number! This would also mean that factoring any number into prime factors would be trivial. Taken together, making these two calculations computable in constant time breaks cryptography.

Well, we could then shift to elliptic curve cryptography. But wait, this computer can also break elliptic curve cypher in constant time. Not only in constant time but it would take the same amount of time to break any encryption algorithm. This means that encryption would be useless.

So our first result:

1. Welcome to a world without any private messaging system

You'd still have old-school privacy by means of physically hiding what you're doing. But sending a coded message in any form whatsoever from email to a post-it note sealed in an envelope is impossible.

For me, the next significant effect is that we can now have perfect simulation (Heisenberg uncertainty principle notwithstanding) of anything. One of the limitations we have today is that some of our theories of physics results in formulas that describe the world at a too low level.

Take for example our understanding of fluid dynamics. The Navier-Stokes equations developed in the 1800s gives us a full description of how fluids (like water or air) behave. But in the 1940s scientists weren't sure if it could explain how bumblebees fly (rule-of-thumb theories developed to allow engineers to design airplanes back then couldn't explain it). It wasn't until we ran some simulations on supercomputers that we began to get a deeper understanding of bee aerodynamics.

You see, the Navier-Stokes equation is an extremely low level description of airflow. It describes how airflow behaves at one point in space. You need to calculate a grid of points to understand airflow in 2D and 3D. As such, it's a complete theory that explains everything, but is useless to human minds because it explains nothing that our mind can intuitively understand.

Having a computer that can simulate anything in 1ns would be a great leap forward in engineering. Not only engineering but even things like climate science and medicine (simulating protein folding for a start then simulating cells to simulating an entire human, or even a city of people at a molecular level to study disease control etc.).

This gives us result number 2:

2. Expect advances in other areas of science and technology

Cure for cancer? Very likely. Reduce carbon emissions by designing better machines? Certainly. Predict the future? Hmm...

Those are just the things that I can think of that would happen if we manage to prove that P = NP. Of course, just proving P = NP simply means that we've proven that for every hard/slow problem there's at least one algorithm that would solve it fairly quickly. So the discovery of P = NP would lead to scientists, engineers and mathematicians scrambling to develop/discover superfast algorithms because we'd know they must exist.

Having a computer magically make any NP-complete algorithm run in P time would mean that we don't even need to try.

Improve this answer
$\endgroup$
16
  • 15
    $\begingroup$ Such a computer couldn't make cryptography useless. Majorly, one time pads would still be viable - so, any parties able to privately communicate once could thereafter communicate securely over public channels - and, in fact, if A trusts B, then A could route messages through B to anyone B can communicate with - so you can build larger secure networks on trust without everyone meeting pairwise. (I can also imagine cryptographic methods using human thought - like CAPTCHAs, but for another purpose - if you can't write a program to do the same, it doesn't matter how much computation you have) $\endgroup$
    – Milo Brandt
    Commented Jun 6, 2015 at 23:41
  • 17
    $\begingroup$ I believe your conclusions about P=NP are wrong. P=NP has nothing to do with the amount of real time a computer takes to run an algorithm. It's about the number of execution steps required, and how that number depends on the size of the input - which is a property of the algorithm, not of the hardware that runs it. You cannot (dis)prove P=NP by using better hardware. Sure, the effect of an instant computer on the real world would be equivalent to making NP problems computable in polynomial time, but the theoretical problem would remain open. $\endgroup$
    – David Z
    Commented Jun 7, 2015 at 12:09
  • 5
    $\begingroup$ @slebetman read and duly noted, I stand by my comment. $\endgroup$
    – David Z
    Commented Jun 7, 2015 at 13:18
  • 4
    $\begingroup$ @DavidZ is completely correct. The OP didn't say every computation ran in the same amount of time. He said every computation ran very very fast -- say a million times faster than any computer today -- so fast as to make computation practically negligible. You haven't shown P=NP, and you haven't found a O(n) general sorting algorithm. $\endgroup$
    – Paul Draper
    Commented Jun 8, 2015 at 3:54
  • 4
    $\begingroup$ Yes. This does not solve theoretical problem P=NP. Remember also that NP are not the hardest problems. They are problems that can be checked in polynomial time and it is not proven yet, that not all of them can be also solved in polynimial time (that P!=NP). There are much harder problems and on the other hand problems in P with big exponent are also hard. When you need $n^{20}$ steps, you need years already for n=10. $\endgroup$
    – BartekChom
    Commented Jun 8, 2015 at 6:33
37
$\begingroup$

So the elephant in the room is the halting problem. Consider a program like this:

while (true) { } // do nothing forever
cout << "Finished" << endl;

This can never halt. It can never print "Finished." Clearly it cannot complete nearly instantaneously.

So the solution has to handle this infinite case. Your solution is to have the machine break, until a reset button is pressed. This handles the easy case, but there be dragons nearby.

Consider that C is turing complete. This means it can describe other turing complete languages. Let's pick Java, because it happens to be convenient for where the story goes next. We can write a program in C consisting of a Java virtual machine with an extra block of text in it. That text is JVM bytecodes, and the virtual machine will run it as code. This is important because now C can do all sorts of nefarious things, like providing the Java sub-program its own bytes as input. Now consider a program with the following pseudocode:

read input as a program
determine if the program will halt or run forever if fed itself as input
if the program would have halted, loop forever
if the program would have looped forever, halt

Let's say I wrote this in Java. I could feed it any program in Java, and it could tell me if it halts. However, what happens if I feed the program itself? If the program halts, it will loop forever. If the program loops forever, it will halt. This paradox is at the center of a decidability problem called the halting problem, and it is a fundamental limit of programming.

Edit: Now this seems to be the topic of much consternation, especially since we're going to make claims about solving the problem. This apparently has even caused this answer to be passed up for selection as the "best" answer. Now consider a program consisting of:

  • A virtual machine, pick the JVM as an example. As a special detail, this VM uses an unlimited precision counter to count how many opcodes have been used. Such counters are well within the realm of computation, given that the memory model of the computer does not specify any upper limit, so I can count using an infinite number of bits.
  • A program under test. This is a sub program which will be run in the JVM, counting how many opcodes are issued
  • A main loop which initializes the VM, runs the program, and then determines if the resulting number of opcodes is finite (which can be written, albeit perhaps calling for an infinite loop).
  • This program then prints whether the number of opcodes executed was finite.

This is an easy to write program, though it is hard to execute it on our mere physical machines. I have written a program, in a traditional computer language, that just happens to require infinite time to execute. By the exact wording in the question, "This device can have the capability to generate true random numbers, and run any program instantly," it must be capable of running this program instantly. This is the actual problem... its a problem with the question which prevents the question from having a meaningful answer until it is properly resolved.

The halting problem is known as a "non decidable problem". There is no way to determine if any arbitrary program halts or loops forever in finite time. The only theoretical way to do it is pushed off to infinity... You have to run the program for an infinitely long time, and see if it halts or not.

However, your supercomputer has oracle capabilities. If a program doesn't halt, the answer comes out instantly. If the answer doesn't come out within nanoseconds, then the operator knows the program actually ran forever, and hits the reset button. Either way, the oracle has answered the halting problem in finite time. This is... big. You can give it programs that would have taken an arbitrary amount of time to run, and it gives you answers instantly. But more interesting, you can give it programs that never loop, but run forever (chaotic systems), and it can give you those answers as well. It can even tell you which ones remain chaotic forever, and which ones eventually loop.

The consequences are... mindblowing. To start, any question which can be phrased in a "formal language" can be answered instantly. Screw AI's cleaning up in Jeprody, now we're talking about solving world-hunger and global-warming sized problems as fast as you can phrase the problem.

Halting also interacts with Godel's incompleteness theorems. This would have religious implications. Many religious statements which are unprovable are suddenly provable with access to a halting oracle. The question of which religion is the "right" one is suddenly within our grasp. One could make observations about our universe, then plug it into a program which simulates all possible universes, and figures out which religions are consistent with the observations. Gather more data, weed out more religions. Then go prove the one religion that is left.

Whichever country has ownership of the supercomputer instantly rules the world. While the path of nations is not fully predictable, it has enough computability that access to that oracle would guarantee flawless victory in every military endeavor the nation undertakes.

So, that's all boring. Way too powerful. How can we cut it down? One answer is statistics. Define two distributions: one for halting programs and one for looping programs. Each distribution should include answering instantaniously, answering in an infinite amount of time, or anywhere inbetween. You can weight the distributions such that the expected run time of a halting program is 1ns, and the expectation of the run time for a halting problem is undefined (i.e. skewed towards infinite run time). The oracle decides the halting problem, then does a draw from that distribution. It then waits that long before announcing the problem.

Now, when it takes a long time for the problem to get answered, it becomes a probability game. Is this an unluckily long halting problem, or is it an infinite looping problem? We only get a statistical answer to this question, so we do not get a definitive answer to the halting problem. This bounds the problem as you woudl like it.

Amusingly enough, if we don't know the distributions (we just know they are statistical), we have a multi-armed bandit problem for anyone seeking to abuse the oracle. This is a well known and rather nifty set of problems, which make for a good story.

Edit: An even more insidious pattern which I did not account for until Samuel's comment: there's no reason we wouldn't build a traditional robot around this oracle. For dealing with large programs which need to collect data from the real world, what if the output of the oracle is a set of instructions for data to collect, plus a new program to run on the oracle with that data (think of it like a singularity event). Now the limiting ability to process data is that we need to reload the working memory of the program each time (USB is actually not a size limit here... it supports 64-bit addressing, but it does limit transfer speeds). Now nothing stops this robot from cruising the world, gathering data, abusing the oracle to do infinite amounts of processing whenever it needs it.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Tim B
    Commented Jun 6, 2015 at 9:18
  • $\begingroup$ @SteveJessop Good point. In my mind the problem is the paradox, but that is not actually technically correct. I have adjusted the wording to better fit the actual definition. $\endgroup$
    – Cort Ammon
    Commented Jun 6, 2015 at 20:02
  • $\begingroup$ Please take further discussion to the chat room. Thanks. $\endgroup$
    – user
    Commented Jun 6, 2015 at 20:26
  • $\begingroup$ Your first program, if we assume infinitely many steps, just writes "Finished". Programs like while(true) a = !a; if(a)... are more tricky. en.wikipedia.org/wiki/Thomson%27s_lamp And what if the loop does not do something periodic. $\endgroup$
    – BartekChom
    Commented Jun 10, 2015 at 7:21
  • $\begingroup$ @BartekChom The examples chosen were intentionally simple. The effect of the halting problem was undervalued during chat discussions on this question, so I wanted to stick to simple examples that are trivial to make sense of. Infinities are tricky enough, much less adding computation, much less adding the kind of real programs you bring up. $\endgroup$
    – Cort Ammon
    Commented Jun 10, 2015 at 15:09
28
$\begingroup$

Almost all of the answers are about theoretical problems with the infinitely fast computer. I see it like this: The machine is an oracle, which reads the source-code and tells you what the solution is.

This won't immediately help with most problems, because most real-world interesting problems operate on huge amounts of data. Someone said the nation with this computer would win any military conflict? How? The difficult part is getting enough information from the real-world into the machine via laughably slow USB-Bandwidth. Even weather-forecasts would need too much time to copy. And this is just the first problem - the second is formulating the program:

I'm a professional programmer and usually my work routine is about 30% writing code and 70% debugging and testing. Which needs a lot of time and a way to check the results. So easily coding a program which determines the flow of the world, would first need someone to write a bug-free program and somehow compress the input so it can be transferred in feasible time.

The interesing part: AI

The much more interesting part would be a task-force to create new algorithms. You could create genetic search algorithms for may problems and let them run so the machine outputs the best code to solve a certain problem. With immense calculation-power we could give the machine complex problems and a fitness function and let it test random code-strings on the problem (like infinite coding monkeys) and it would find the best possible program to solve the problem.

So we could first develop an AI which could optimize communication with the device and could be run on our normal computers, with better access to real-time input and then use this AI to produce a real-world simulation to solve problems like creating better hardware and solving physical problems.... on to world domination!!!

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ If we do it right, we could achieve the singularity in some mere months!!! :-) $\endgroup$
    – Falco
    Commented Jun 5, 2015 at 11:34
  • 1
    $\begingroup$ Huge +1 for the practicality aspect overlooked by several of the other answers. $\endgroup$
    – krb686
    Commented Jun 7, 2015 at 3:00
  • $\begingroup$ And along the same line of thought, we are also limited per the OP that it outputs all of the data into a single output file "output.txt". There would be some massive limitations on using this device in the manner mentioned by some in terms of "brute force all possibilities to solve problem X". It's no different than writing a program to generate all possibilities of ASCII characters for a block of text and leaving it up to us to discern which cases are fantastic novels versus random gibberish. $\endgroup$
    – krb686
    Commented Jun 7, 2015 at 3:06
  • 1
    $\begingroup$ @thirtythreefourty not quite true. If the number of possible inputs vastly exceeds the number of possible hashes you will have a lot collisions. So the program will find a quintillion inputs marching the same hash. Which one to choose? $\endgroup$
    – Falco
    Commented Nov 12, 2015 at 8:10
  • 1
    $\begingroup$ @Falco true, but in practice I bet you would be able to provide enough metadata about the inputs (must be valid JSON, has this size, has this hash, etc), that you could get an exact match. $\endgroup$
    – thirtythreeforty
    Commented Nov 18, 2015 at 20:20
19
$\begingroup$

I would use this computer to write code.

Due to the limited i/o rate of the computer, hooking it up to real world problems will be problematic due to the sheer amount of data that needs to be passed in order to properly assess these issues.

However, if I pass in a compiler and a set of objectives, I can pass in the following program to the computer in order to generate code whose outputs meet the objectives:

program = '0';
do{
  compile the program
  if it compiles:
    run it.
    if it runs:
      see if if satisfies the objectives
      if it does:
        return the code!
   else:
     increment the binary string 'program' by one.
} while(program.length < what can be read out in a day/month/year);

Since our computer is arbitrarily fast, we can use arbitrarily ugly code on it. In this case, I would simply generate every byte string short enough to be read out in whatever time I have allocated to use the computer to generate this code. The computer will generate every such string in order from smallest to largest, so I will not only find a code to solve my problem, but find the shortest such code. I can even give my computer a goal like 'find the fastest running code below a certain length that solves this problem.'

I can use the computer to write things like:

  • The best version of every algorithm
  • The best versions of algorithms we haven't even discovered
  • Strong AI.
Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ It would be hard to write, for example, code that determines the validity of an AI. $\endgroup$
    – BWG
    Commented Jun 5, 2015 at 15:39
  • 7
    $\begingroup$ I like this. Basically a brute force approach to writing code. $\endgroup$
    – Ajedi32
    Commented Jun 5, 2015 at 16:41
  • 4
    $\begingroup$ You need an absolutely secure VM to run that freshly written code, otherwise you'll quickly end up running some malware :D $\endgroup$
    – Display Name
    Commented Jun 5, 2015 at 22:50
  • 1
    $\begingroup$ You don't even need to restrict the search to terminating programs, you can avoid the need to do anything clever and just dovetail all the programs (en.wikipedia.org/wiki/Dovetailing_%28computer_science%29). Instead of trying to run the first one to completion, followed by the second, etc, run one step of the first program, then one step of each of the first two programs, then one step of each of the first three programs, etc. Then you can still use one go of the machine to find the fastest program, below a certain length, that solves the problem. $\endgroup$
    – Steve Jessop
    Commented Jun 6, 2015 at 15:05
  • 1
    $\begingroup$ 'see if if satisfies the objectives' <-- still requires some programming :-( $\endgroup$
    – M.Herzkamp
    Commented Jun 8, 2015 at 12:33
10
$\begingroup$

Physicists and chemists use ab initio calculations; they are extremely accurate, but incredibly computationally expensive (a friend of mine used to wait days for his calculations on a surface of several hundred atoms to complete). With your computer, we can calculate the bulk properties of every material imaginable. We would find superior (in every regard) metal alloys, room temperature superconductors if they are possible (and don't rely on unknown exceptions to quantum mechanics), higher energy density battery materials, and so on.

Of course, none of this necessarily means you know how to make any of these materials, but round 2 can be a simulation of every conceivable combination of materials, temperature, pressure, etc... and return a list of the cheapest processes for producing every material of interest.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Oh I think you could do so much more than simulate atom interactions... $\endgroup$
    – Neil
    Commented Jun 5, 2015 at 16:06
  • $\begingroup$ Certainly, this is just one use of the supercomputer. An incredibly powerful one though. $\endgroup$
    – frodoskywalker
    Commented Jun 5, 2015 at 16:36
  • $\begingroup$ Wow this is a very good idea! +1, too bad I can only select one answer though because theres so many useful answers here. $\endgroup$
    – vero
    Commented Jun 6, 2015 at 2:20
  • $\begingroup$ @Neil As of today, simulating atom interactions is the function of most (if not all) supercomputers, and as frodoskywalker says, they only can handle few atoms, and simulate short times. If this magic supercomupter existed, defintely it would be used to run every physics/chemistry/molecular biology simulation imagined ever, and we would beneficit from new materials and drugs. $\endgroup$
    – Bosoneando
    Commented Jun 6, 2015 at 9:11
  • $\begingroup$ @Bosoneando True, this is the immediate application, but I can't imagine this being the best use. If we could find the cure for cancer in a drug with enough simulation time, we would already have warehouses full of supercomputers processing just that. It means there are no immediate benefits, only research. Using such a hypercomputer for simulating molecules is like saying that upon the invention of the telephone, that the best known application is being able to call another room in the same house without having to yell. $\endgroup$
    – Neil
    Commented Jun 8, 2015 at 7:14
5
$\begingroup$

A lot is going to depend on access. Will it be free? Nah. NASA will hang on to it.

As mentioned cryptography will end. So will public stock trading. Simulations will be as powerful as the I/O allows.

Furthermore perfect aeroplanes, heat shields, geographic exploration, weather forecast, DNA research for the owner. And a leap ahead for biology, astronomy, reliability engineering and robotics, and [undisclosed military application].

Plus lots of money earned from renting out a few computing slots, say 1%.

But in the end it will allow a Monte Carlo learning curve that will give us "The Future Machine" which will result in either world peace, world domination and/or WWIII.

I'm taking bets that it will eventually end under a mile of glow-in-the-dark rubble. We can then rename it to "Cassandra".

Improve this answer
$\endgroup$
2
  • $\begingroup$ In the case of an infinite loop I expect the output to say just that after that single ns. $\endgroup$
    – Bookeater
    Commented Jun 5, 2015 at 6:19
  • $\begingroup$ +1 for putting it simply, considering financial ramifications and pointing out the likely conclusions based on human nature (really enjoyed the Cassandra reference) $\endgroup$
    – thanby
    Commented Jun 5, 2015 at 20:01
5
$\begingroup$

If you allow the output to be **ERROR program never halts**. What you have is essentially a Hyper-Computer.

The device that most closely matches your setup is a Zeno machine. After 1 ns you have either the result of the computation or it's already "crashed".

This stands above the Turing machine in the computational hierarchy and bypasses the Halting problem entirely.

The result of having such a machine available means that all computational tasks that you can think of will be able to be solved as fast as you can port them to the machines language and transfer them in.

This means that is the NSA has access to it then they don't need to insert vulnerabilities in crypto standards. As most encrypted data can be decrypted. The One-Time pad will remain safe however.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ To make our cube a hyper-computer, all you would need is a reset button. For, if it could run any program instantly, then the fact it had failed to do so would mean the input program never halted - so just hit the reset button. $\endgroup$
    – abcdefg
    Commented Jun 6, 2015 at 4:45
4
$\begingroup$

This is only a partial answer, but as phrased this question doesn't make sense. Take the simple program:

while(true) {}

This program will never terminate no matter how long or how fast you run it. (Another example would be any game, which only ends when the user presses the quit button.)

Now, before you simply say that the device can instead run programs, say, 1 trillion times faster than our best supercomputers, let me warn you that that won't help much. The kind of programs you're probably thinking of running are those that are categorically beyond current computers, like working out the best route for a travelling salesman that wants to visit hundreds of cities. Unfortunately, that and many other similar problems grow exponentially.

So, if we assume the base of the exponent for a travelling salesman algorithm is 2 (not accurate, but easy), how many extra cities could the device allow us to solve for in the same amount of time? Well, about 40. (2^40 is close to a trillion.) So however many cities we could have solved for before, this device allows us to add just 40 to that.

Ok, so if we instead say that the device can instead just look at the program and decide what the output will be without actually running it what could you do with it? Well, if we ignore the implications of the fact that this would be doing something mathematically impossible (and would therefore allow things like making 2 equal to 3) the best thing would be to look up a list of NP-complete problems. Out of those, the most immediately important would be that it would render all cryptography useless.

If you don't want to ignore the mathematically impossibility, there are some other possibilities, but they get fairly complicated. The simplest one would be if the device functioned as a SAT oracle. (SAT is the boolean satisfiability problem.) This would allow for any NP-complete problem to be solved instantly, but would require the programmer to put it in a specific form first. (It's probably still mathematically impossible, but no one's proven that yet.) It'd still have many of the same implications, but there are still many problems it couldn't solve.

Improve this answer
$\endgroup$
11
  • $\begingroup$ I said in the question that NASA acquired the device, I assume that NASA would actually try to use the device, not try to break it. Lets assume that when giving a program that never halts, the machine breaks and you have to press a reset button to use it again. People wont run games on this device because USB does not have enough bandwidth for a monitor, and additionally the device only outputs to a file. Thanks for the answer :) $\endgroup$
    – vero
    Commented Jun 5, 2015 at 5:01
  • 3
    $\begingroup$ @Rodolvertice I'm going to try to word an answer, but fair warning: this issue of halting is WAY deeper than you think it is. The handling of it makes the difference between "universe shattering consequences" and "just another brick in the wall." $\endgroup$
    – Cort Ammon
    Commented Jun 5, 2015 at 5:07
  • $\begingroup$ There's two problems with that first point. How would they know that that would break it? (I guess it doesn't matter much if they can just reset it though.) And second, how would they know if the program was infinite or not? That's called the halting problem, which is provably unsolvable, and there are interesting programs that you could run that might not halt. (Games were merely an example of an infinite loop.) Ninja'd, but as Cort said, the issue of halting, and the theory of computation in general, is far from simple. $\endgroup$
    – Joshua Taylor
    Commented Jun 5, 2015 at 5:08
  • $\begingroup$ Actually, a machine that would break if given an infinite program is still mathematically impossible, as that still gives you a definite answer to whether or not the program would halt. $\endgroup$
    – Joshua Taylor
    Commented Jun 5, 2015 at 5:11
  • 1
    $\begingroup$ That's why I marked my post as only a partial answer. (I probably would have only put it as a comment, but I don't have enough reputation for that.) And it would shatter the universe in a way if it output bytes when it should be mathematically impossible for it to do so. (BTW, mathematically impossible is a step or two up from physically impossible, and another step or two up from practically impossible.) I did mention it above, but anything on this list would be instantly solvable, as well as all modern cryptographic schemes. $\endgroup$
    – Joshua Taylor
    Commented Jun 5, 2015 at 5:16
3
$\begingroup$

I think y'all are all missing something here.

This device would, if its existence were made public, essentially be the end of the world. Given human nature and the axis of greed and fear that drives most of government, business and society, this device would be the cause of a truly staggering amount of conflict. Including the use of nuclear weapons to destroy any facility thought to contain it.

EDIT:

At the end of the day people are interested in their own self interest. This device would give the owners knowledge and tools to impose their world view upon everyone else. People who didn't own the device would fear it and the power it brings. That is a recipe for Armageddon.

Yes, I realize that this is not the most popular or positive world view.

My point is not about individuals, but about societies, governments, and/or businesses. All of those groups exist to further their own interests.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ While this does qualify as an answer, it's not great at the moment - can you explain why you think this is? $\endgroup$
    – ArtOfCode
    Commented Jun 5, 2015 at 17:20
  • $\begingroup$ If NASA received this device and just disguised it as a quantum computer that they built, does the government have the right to confiscate it? If not, then I do not think that it would result in global decimation. I assume the people at NASA are ethical, but you are right, people are greedy. $\endgroup$
    – vero
    Commented Jun 6, 2015 at 2:34
1
$\begingroup$

I'll assume the computer is just really fast, not infinitely fast (since that is just weird as other answers point out).

If it's sufficiently powerful, pick your favorite open problem, and perform an exhaustive search of all possible algorithms to solve said problem (not just searching for a specific solution, but for the actual algorithm to solve it), rate the potential algorithms by success rate, performance, and length to find an efficient one. Use genetic programming to optimize the search process. Let the machine churn for a few days or weeks, if it finds a working algorithm, poof; the problem is open no more. If it finds nothing, then (depending on the computer's speed) it's likely no efficient algorithm exists, or it's just really hard to find; either way, we stand to learn a lot more than we started out with, and (bonus!) if the machine is ever taken away from us, we can still use its results.

One would need to look at the algorithm the computer found to understand why it works, but that reverse-engineering task is peanuts compared to finding the algorithm in the first place (because we told the machine to search for not-too-long algorithms, and experience shows us that most algorithms to solve problems are actually fairly short: you could describe most of them in two or three pages of code).

Needless to say, it would have to be really fast for this to be worthwhile, but if it's really as fast as you claim then it could plausibly allow humanity to quite literally brute-force its way to knowledge, at least. So I can certainly see this machine leading to unparalleled advances in the field of theoretical mathematics at least (which in turn can be put to work in more practical applications).

Improve this answer
$\endgroup$
1
$\begingroup$

If I was a Monty Python fan working at NASA, then I would as "What is the unladen air speed of an African swallow".

Seriously though, there are already many answers here featuring worthy questions on cancer, etc, so I'll take a different approach.

Our cube is capable of faster-than-light information processing.

If I was NASA, then my first question would be "What is wrong with our Theory of Relativity?". According to our understanding of relativistic effects, there would be no need to ask any questions since the faster-than-light cube should be able to answer our questions before we ask them. Since this is not happening, there must be something wrong with our theories.

If the cube answered "Nothing is wrong with your theory of relativity", then I would conclude that the cube must be travelling backwards in time (relative to us), so I would ask "What is wrong with The Second Law of Thermodynamics". If the cube answered "Nothing is wrong with your second law", then I would probably throw a chair at it. After composing myself, I would ask the cube if it was in fact travelling backwards in time, to which it would no doubt reply "Time is not part of reality".

If I was a philosopher working at NASA, then I would ask one of the big questions of philosophy, such as "Why is there something rather than nothing?". If the cube was able to answer this question in finite terms, then the question is - will we understand the answer? The issue of understanding an answer would be a big hurdle with all difficult questions.

If I was a mathematician working at NASA, then I would ask "Is Riemann's Hypothesis true" and if so, ask for a proof in finite terms. This probably sounds obscure to a general reader, but it would have profound effects on the subject.

A question with potentially profound implications would be "What is the fate of mankind"; "Are we alone in the observable universe"; ... I've already gone on too long.

Improve this answer
$\endgroup$
12
  • 1
    $\begingroup$ You can't ask the machine questions, you can only run programs on it. If you can formulate a program that asks each of those questions programatically, (which would be very tough to do), then this answer would apply. The cube doesn't know what the second law of Thermodynamics is etc. $\endgroup$
    – vero
    Commented Jun 6, 2015 at 2:32
  • $\begingroup$ @Rodolvertice Fair enough. It's your question. However, it seems a bit odd that you should have a computer capable of executing all computable functions in an instant and yet is unable to understand natural languages. That's a bit like having a faster-than-light space ship, but only using to go down to the corner shop and never exceeding 30 miles per hour. Such a computer must, by definition, know everything that is knowable. $\endgroup$
    – abcdefg
    Commented Jun 6, 2015 at 16:50
  • $\begingroup$ @NickR The problem of natural language processing isn't speed. A constant time computer won't be necessarily be better able to understand natural language. Nor would it provide a computer with the capability to understand relativity or the scientific method, or to conduct appropriate experiments, etc. It just means that given an arbitrarily long set of simple mathematical operations, it can give you the result in constant time. $\endgroup$
    – smithkm
    Commented Jun 6, 2015 at 22:30
  • $\begingroup$ @smithkm The machine described is capable of executing any computable function - and I use the term computable function in the strict mathematical sense. Our scientific theories are mathematical formalizations and therefore computable. The machine would therefore be able to understand these theories. We may be restricted in what we can input into the machine, but that would not restrict the machine's internal processing and its ability to add information. I was really just trying to have a bit of fun with the question since so many answers had already been posted. $\endgroup$
    – abcdefg
    Commented Jun 6, 2015 at 23:48
  • 1
    $\begingroup$ @NickR Doing the computations doesn't tell you whether the model matches reality, it just tells you what the model predicts. More predictions to compare to reality will certainly aid in checking the models, but the computer couldn't do the scientific method on its own without conducting experiments in the real world. This would also require a "scientific method program" which would be a fairly impressive feat of AI even with a constant time computer. $\endgroup$
    – smithkm
    Commented Jun 8, 2015 at 7:07
1
$\begingroup$

Depends a lot on who has control over the computer.

It will definitely be very interesting for solving all kinds of computationally heavy problems.

  • No encryption is safe anymore.
  • Everything that can be described mathematically can be calculated, the brute force way. Less need for finding optimal algorithms for those that control the device).
  • Pi can be known to a number of digits that can reasonably be transferred and saved on a USB device.

Now a lot of interesting problems require the processing of large amounts of data. There your USB port as only input becomes a bottleneck. I assume there is no way to upgrade the device, so it'll be stuck with the transfer speed of USB. Expect a surge in research for compression and for automated data generation.

Also, how much internal memory do we have to work with?

Somehow, I also expect someone to use this for porn, but my imagination is unfortunately lacking here.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The internal memory is not bounded. $\endgroup$
    – vero
    Commented Jun 5, 2015 at 8:27
  • $\begingroup$ Not sure why you think we could calculate the movement of heavenly bodies accurately. Sensitive dependence on initial conditions is a basic principle in chaos theory, and given that a) we could never measure the initial conditions accurately (eg exact position and velocity of the bodies at time t=0), and b) your black box is (as far as I understand from your question) still a finite machine, then you would have exactly the same issues of divergence as we have with our current computing ability. Still, your other points are interesting. $\endgroup$
    – Avrohom Yisroel
    Commented Jun 5, 2015 at 9:44
  • $\begingroup$ @AvrohomYisroel: you're right, so I threw it out. Thanks for pointing it out! I thought that calculations of multiple interacting masses was almost impossible due to the complexity and I never even thought about chaos theory. $\endgroup$
    – HSquirrel
    Commented Jun 7, 2015 at 15:30
1
$\begingroup$

Cryptography

Cryptography relies on problems that are prohibitively expensive to solve, in terms of computation time.

Someone with access to this computer could break anything with public key encryption. An unscrupulous individual could hack his way to extreme wealth. A government may use this to monitor otherwise secure communications.

Breaking encrpytion was the purpose of one of the very earliest computers, during World War II.

Simulations

...of all sorts of stuff. Take a look at anything being run on a supercomputer today.

Weather simulations will mean accurate weather reports.

Physics simulations could help us understand quantum dynamics, the cosmos, etc.

Engineering simulations could mean better engines, solar panels, etc.

Biology simulations could mean cures for many diseases.

Math proofs

There are a finite number of math proofs of a given length. With a fast enough computer, you could search for proofs of unsolved problems, like P=NP, or the Riemann hypothesis.

Graphics

Video processing would be quite fast.

And you couldn't ask for a better gaming machine.

Artificial intelligence

With massive amounts of compute available, AIs can be much, much better.

In the end, the usefulness of this computer will depend a lot on its I/O abilities. If it had similarly fast I/O, the entire world could use it for computing. Otherwise, it wouldn't been able to solve as many problems as quickly, but it would still be game changer for the overall advancement of mankind. As Thomas said, we would essentially be brute-forcing our way to knowledge.

Improve this answer
$\endgroup$
1
$\begingroup$

If there is only one, with a USB connection only, the damage wouldn't be too bad. It was said that cryptography would be broken: Yes, but only one message at a time. So we would have to think about a communication protocol where a message from A to B can be decrypted by this computer, but where that decryption wouldn't give any hint that a lesser computer could use to decrypt other messages. I would be sure that can be done.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .