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.

gjm 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: gjm 21 August 2015 02:40:30PM 2 points [-]

Your scheme may well he more powerful than a Turing machine (i.e., if there were something in the world that behaves according to your model then it could do computations impossible to a mere Turing machine) but much of what you write seems to indicate that you think you have implemented your scheme. In Python. On an actual computer in our universe.

Obviously that is impossible (unless Python running on an actual computer in our universe can do things beyond the capabilities of Turing machines, which it can't).

Could you clarify explicitly whether you think what you have implemented is "more powerful than every supercomputer in the world" in any useful sense? What do you expect to happen if you feed your code a problem that has no Turing-computable solution? (What I expect to happen: either it turns out that you have a bug and your code emits a wrong answer, or your code runs for ever without producing the required output.)

Comment author: ImNotAsSmartAsIThinK 26 August 2015 11:42:47PM *  0 points [-]

I'm sorry that I over estimated my achievements. Thank you for being civil.

What do you expect to happen if you feed your code a problem that has no Turing-computable solution?

I'm actually quite interested in this. For something like the busy beaver function, it just runs forever with the output being just fuzzy and gets progressively less fuzzy but never being certain.

Although I wonder about something like super-tasks somehow being described for my model. You can definite get input from arbitrarily far in the future, but you can do even crazier things if you can achieve a transfinite number of branches.

If you're still interested in this (I doubt you are, there are more important things you can do with you are time, but still) you glance at this reply I gave to taryneast describing how it checks if a turing machine halts. (I do have an ulterior motive in pointing you there, seeing as I want to find that one flaw I'm certain is lurking in my model somewhere)