↑ comment by ImNotAsSmartAsIThinK ·
2015-08-26T23:30:29.749Z · LW(p) · GW(p)
For some strange reason, your post wasn't picked up by my RSS feed and the little mail icon wasn't orange,
Sorry to keep you waiting for a reply for so long.
The Halting proof is for Turing machines. My model isn't a turing machine, it's supposed to be more powerful.
You'll have to mathematically prove that it halts for all possible problems.
Not to sound condescending, but this is why I'm posting it on a random internet forum and not sending it to a math professor or something.
I don't think this is revolutionary, and I think there is very good possibility there is something wrong with my model.
I'll tell you what convinced me that this is a hyper-computer though., and I'll go a ahead and say I'm not overly familiar with the Halting inasmuch as I don't understand the inner workings as well as I can parrot facts about it. I'll let more experienced people tell me if this breaks some sort of conditional.
What my model essentially does is graft a time-travel formalism onto a something turing-complete. Since the turing -complete model of your choice is a special case of the model we just constructed, it's already turing complete. And the formalism itself already specifies that information can travel backwards through time, what has to be proven is that an algorithm can be constructed that solves the halting problem.
With all of that, we can construct an algorithm based off of the following assumptions about time travel
Inconsistent timelines "don't exist"*
A timeline is inconsistent if it sends back different information than it receives
If more than one timeline is consistent, then all are equally realized.
I have no idea if you read through the ramblings I linked, but the gist was that to simulate the model, at any given timestep the model receives all possible input from the future, organized into different branches. 'possible' is a important qualitfier, because the difference between the model being exponential in the size of the memory and exponential in an arbitrary quantity constrained to be smaller the size of the memory is whether you can tell if a given bit of memory is dependent on the future by looking at only the current state.
Next, I'll point out that because the model allows computation to be carried out between receiving and sending messages, you can use the structure of the model to do computation. An illustration:
Suppose X is a turing machine you are interested in whether or not it halts
1. Receive extra input from the future (in the form of "X will halt after n timesteps" )
- If null, goto 3 with n = 0
2. Is it properly formatted?
- If not, halt without outputting t the past. (Halt.)
3. Simulate X for exactly n timesteps
If it halts before then, output "X will halt after m timesteps" where m is the number of cycles before it halted. Halt.
If it doesn't halt after n timesteps, output "X will halt after n+1 timesteps". Halt
I'll note this algorithm only appeared to me after writing my posts.
Here's how it works.
We can number each timeline branch based off of what it outputs to the past. If it outputs "X will halt after y timesteps" then it is machine y.
If X doesn't halt, machine y will simulate X up until y-1 timesteps, and output that it wil halt after y timesteps.
The above point should be emphasized. Recall above how a timeline is inconsistent and therefore "non-existent" if it's input doesn't match it's output. Thus, for a non-halting X, every machine y will be inconsistent, and the hyper-computer will halt immediately (things are a bit fuzzy here, I am 80% confident that if there is a problem with my model, it lies in this part).
If it halts at t=z, then y=z is that only consistent timeline. For timelines y>z, they output y+1, for timelines y<z, they output z. Making y=z a kind of attractor.
My problems with this timeline are as follows:
I haven't been able to formulate the algorithm, without a) having every timeline inconsistent when the machine halts or b) the actual output uncertain (if it says it halts at z, you know for a fact it does, but if it says it doesn't halt, then you can't be sure)
"non-existent" timelines have casual weight.