You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

PhilGoetz comments on Bragging thread August 2015 - Less Wrong Discussion

3 Post author: philh 01 August 2015 07:46PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (43)

You are viewing a single comment's thread. Show more comments above.

Comment author: ImNotAsSmartAsIThinK 13 August 2015 05:10:23PM *  0 points [-]

I wrote a hypercomputer 60-ish lines of python. It's (technically) more powerful than every supercomputer in the world.

Edit: actually, I spoke too soon. I have written code which outlines a general scheme that can be modified to construct schemes in which hyper computers could possible constructed (including itself). I haven't proven that my scheme allows for hypercomputation, but a scheme similar to could (probably), including itself.

Edit: I was downvoted for this, which suppose was justified.

What my code does is simulates a modified version of CGoL (John Conway's Game Of Life). It's modified so that information can (technically) flow back through time. It's very similar to what EY outlined in the second section of Casual Universes, except my algorithm is much simpler, and faster (it'd be even faster if I hadn't done a half-assed job of coding it and choose a good language to write it in).

My scheme is more general than the code. I've tried explaining it on /r/cellular_automatta here and here, with a passable degree of success.

The scheme itself is capable of hypercomputation with the right underlying rules. I'll write a quick demonstration, assuming you've read Casual Universes, and my explanations

  • in order to be capable of hyper computation it must be capable of regular computation. CA have already been proven to be Turing machines in disguise so I'll take this for granted.

  • by the above, you should be able to construct a simulation of any turing machine in the CA. Again, this is a fact, so I'll take it for granted

  • I've already said that the algorithm involves backwards information flow (time travel by another name)

  • by the above, we can construct a state in the CA which simulates a given Turing machine, then pipes it's output back in time to a finite time after the simulation started

  • if we modify the simulation to instead just pipe the fact that the machine produce output, and nothing else (one bit), we can know before hand that a turing machine produces output.

I'd think anyone reading this is familiar, but this is called the Halting Problem, I think (I could be wrong, but I am highly confident I am not) my scheme solved it.

The only real problem is that if the T-machine doesn't halt, neither will the one we constructed, but it will produce output after an arbitrarily finite amount of time.

This does mean my scheme is more powerful than an Turing machine. For instance, it can compute the busy beaver function to a proportional amount of values.

You can look at the code here, but it's messily and hacked together. I only wrote it as a proof of concept in the first /r/cellular_automata thread I linked.

Comment author: PhilGoetz 21 August 2015 04:08:30AM 1 point [-]

Could some other people who have read Causal Universes comment on whether EY implies in it that hypercomputation is possible? What is hypercomputation?

Comment author: gjm 21 August 2015 02:46:52PM 2 points [-]

EY doesn't imply that hypercomputation is possible in our universe. He does imply that there are logically possible universes in which hypercomputation is possible. Hypercomputation is any computational process that is able to evaluate at least one non-Turing-computable function.

(That last definition may be unhelpful in practice. If our universe is finite then it can't contain anything that's even Turing-powerful, never mind capable of hypercomputation. If our own lifespan and perceptual powers are finite then there's no way we could ever know anything was doing hypercomputation.)

Comment author: PhilGoetz 21 August 2015 05:09:24PM *  1 point [-]

Hypercomputation is any computational process that is able to evaluate at least one non-Turing-computable function.

What about computing a Turing-computable function in O(m) time, where a Turing machine needs O(n) and m < n? Does quantum computation count as hypercomputation? The Wikipedia page seems to say no.

Comment author: gjm 21 August 2015 06:40:32PM *  0 points [-]

I'd agree with Wikipedia. After all, there are plenty of other physically-realizable models of computation that are equivalent to Turing machines in terms of what they can compute but substantially inequivalent in terms of how long it takes.

[EDITED to add:] ... Though I think anything you can do in a Newtonian universe can be modelled on a Turing machine with at worst a polynomial-in-problem-size slowdown. So there might be something to be said for counting as "hypercomputation" anything that, e.g., can evaluate all computable functions in constant time. But that isn't the usual use of the term.