There is a general theorem that says that for any computation, you can write a program that executes that computation on its own source code. The quine is only a special case.

Actually I think the 'ace' in Paper/Hackpad/Etherpad is a different thing called ace.

Hah, whoops - you’re right of course:

https://github.com/ether/pad/tree/master/infrastructure/ace

> ACE2 is EtherPad's editor, a content-editable-based rich text editor that supports IE6+, FF(2?/)3+, Safari(3?/)4+. It supports collaborative editing using operation transforms (easysync2), undo/redo, copy/paste.

> The name "ACE2" is because this is a rewrite of aiba's original content-editable AppJet Code Editor.

www.scottaaronson.com/papers/ctc.pdf

Shows that (with or without quantum computing) you can do all of PSPACE using a CTC (in polynomial time) and no more.

This is the key result in this conversation; this should be higher. Basically: if we insists on Deutsch's causal fixed point propety of CTCs, they do not give you P=NP, they give you P=PSPACE. That is, all problems which can be solved in polynomial space can now be solved in polynomial time, and vice versa.

So for a time-travel computer to give P=NP or P=O(1), it would have to violate Deutsch's causality criterion. I have almost zero knowledge of either field, but it sounds to me like it makes Deutsch's model more plausible.

PSPACE is bigger than and contains NP. You still don't get ANYTHING=O(1), though.

https://en.wikipedia.org/wiki/NP_(complexity)#Relationship_t...