"The question of which religion is the "right" one is suddenly within our grasp." - that's overoptimistic. Putting aside the issues with whether the magic box's answers are trustworthy when no understood device can check its work, and putting aside the human psychology issues that would make people just reject the box's answers anyway, if your search space includes models of the universe where things can just happen "miraculously" or "because [diety] wills it", the box won't be able to decide that our universe is inconsistent with such a model.

Forget infinite loops; that's an easy case, and we can perhaps even handwave them away by saying that the computer is somehow sophisticated enough to detect them. Try something like (C, here) time_t tStart = time(NULL); while(time(NULL) < tStart+42) { /*busy wait*/ } printf("Hello World!\n"); -- given that time(time_t*) returns the number of seconds since the epoch, there is no way this can finish in 1 ns, no matter how powerful your computer is, but (absent bugs in the standard library or pesky issues like integer overflows) it is guaranteed to finish in "reasonable" time on any system.

I'm not sure this is an elephant, and I don't even think it needs a reset button. As you say, this is an Oracle, not a super fast Intel. Put an non-halting program in, and it can instantly generate a text file containing +++ OUT OF CHEESE ERROR +++ REDO FROM START +++ - that's my reading, anyway. Unless the final reveal is it's a Pentium 10,000 sent back in time.

@MichaelKjörling to "fix" that you disallow time dependent queries in the language. The device is then a stateless black box.

The Halting Problem can be resolved much more simply by refusing the requirement that the computer be able to run programs in "any" language. Give it a non-Turing-complete instruction set (e.g.). Trying to compile C to this instruction set might or might not produce a correctly-working program, but that's a compiler issue; there are no more problems on the computer's side, as every computation halts. Turing-completeness is wildly overrated for engineering purposes.

@ratchetfreak But this is what we've been given. A computer that can run any program in 1 ns or less, despite any possible program you could write. Essentially it's a paradox. Though I would like to meet the poor schmuck that puts an unhalting program to see what happens only to cause the fastest computer in the world which cannot be opened to loop endlessly. "Oops.. I guess I'll go grab a box to put my office supplies in..."

Re: halting problem issue - let's posit that the computer solves problems by opening them in a sub-universe and executes them there. Because time in the sub-universe proceeds at right angles to time in our universe the program still takes zero execution time in our universe even when run to infinity in the sub-universe (the perceived 1ns run time is basically sub-universe set-up time). In this case a non-halting program would still take zero time to execute. This also deals with the issue of how a program can wait for a fixed amount of time and still complete in 1ns.

@Neil but you don't need time since epoch queries to the turing complete (proof, the turing machine itself doesn't provide a way to get the current time) so michael's argument is kinda invalid.

@ratchetfreak I see what you mean, though he did use the word computer and not turning machine, so I have to assume that means that unless otherwise stated, it is as a normal computer (or supercomputer if you prefer).

Assuming that the machine is a super-fast Turing machine is a fallacy IMO. Instead it should be assumed to be a HyperComputer

"solving world-hunger and global-warming sized problems as fast as you can phrase the problem". I highly doubt computational power is what's stopping us here, how can you possibly input all the required data on to a flash drive? The limiting factor here is how to write a program that solves the world's problems, not how quickly it finishes.

@Samuel I didn't write to this, but what if the output is instructions to us on what data to collect, and a program to run with that data on the oracle? Now you can start using otherwise non-decidable functions in your logic to determine what data to collect. That approach would be the singularity on steroids.

It's simple to imagine, but I don't see how a computer can give you information that you didn't give it. Did you include all possible things to ask for and it chose from that list? I agree that an AI is the way to go. At least a new USB protocol designed by a genetic algorithm.

@Samuel: From an information theoretic perspective, it can't give you any information you did not give it. However, from a perspective of being able to do infinite computation in a finite time, it can process all information you give it to find the most valuable information within it. It can then use this to ask you to go out and get new information. It starts to be reasonable to treat this as a supreme brain, seeking out input just like a human goes through the world using his or her eyes and ears.

I like the edit very much. I think it should be the main answer. Build a robot around the box and pass any sufficiently complex computation through the USB interface.

I think you misunderstood the halting problem. The point of the halting problem is that you cannot write a program that determines if another program will half or run forever. I'm not bothered by the fact your program needs infinite time to get to a answer, I'm bothered by the fact you wrote this program. I can, however, prove your program is wrong. I just feed it to the above mentioned box. If the box runs forever, your program is wrong and should have terminated. If the box stops instantly, your program is wrong and should have ran forever. It's wrong either way.

@Dorus I understand the halting problem fully. The issue is demonstrating just how much trouble it causes the original question. Halting involves working with a non-recursively enumerable set, making the problem undecidable. However, it is trivial to write such a program in a common programming language, as specified by the OP. If this oracle is capable of solving it (as required by the question), then that oracle is at least a hypercomputer. A Turing computer that can run infinitely long is one such hypercomputer.

Or, in short for, you can write a program that determines if another program will run forever or not. However the halting problem which that program seeks to solve is in the "non-decidable" class. The first entry in wikipedia's hypercomputers list (en.wikipedia.org/wiki/Hypercomputation) is "A Turing machine that can complete infinitely many steps."

Oh I agree that the box can certainly act as a oracle, you just cannot simulate these oracle capabilities in your program even if it runs on the box.

@Dorus Did I make a statement that suggested I could? If so, I should am mend it.

Yes, no, I'm not sure any more. My brain kinda wend on alert when I read this: "Now consider a program with the following pseudocode:" [...] "determine if the program will halt or run forever if fed itself as input" [...] "Let's say I wrote this in Java."

@Dorus Yeah, the wording is sharp edged, isn't it. Its actually trivial to write the program in Java, if you accept an infinite runtime. Count the number of opcodes executed. If its finite, the program halted. If it's infinite, the program did not halt, by definition. Normally that doesn't count as "solving the halting problem" because it requires infinite steps to do (which is forbidden in decidability problems). No rules have been broken by writing it. However, it's still a valid program, and the oracle exposes whether the program halts in finite time, so the excitement starts =)

You cannot count to infinity, not with Java or C++ or any other turning complete programming language. Not even mathematical. There is no very large number, that, when you add one to it, becomes infinity.

Actually, you can. In mathematics, \aleph_0 is known as "countable infinity." It is the infinity that can be reached using nothing but repeatedly adding one. It's the infinity of the continuum, \aleph_1 that you cannot ever possibly count to. There is a group of individiuals called ultrafinitists which believe what you say (that there is no such thing as the Natural numbers), but they are the minority in mathematics.

@Dorus (now that this is in chat, I'm not certain if there's a way to notify you that I have an answer to you, so I'm going to try this, and see if it works)