M.H. Freedman “Limit, Logic, and Computation” *Proc. Nat. Acad. Sci.* **95**(1) 95-97 (6 Jan 1998), available online at *Proc. Nat. Acad. Sci.* and Freedman’s Microsoft Station Q home page

Alas, I’m pretty sure this hasn’t been a fruitful research programme given that I’m pretty sure Freedman never published further on the topic and the paper above was only cited 4 times, and none of those papers which cited it were extensions of its ideas.

But perhaps other readers know of similar approaches.

]]>Kindly remind us what PA means.

]]>Now, it is implicit in Goedel’s definition that F(x1, x2, x3) has the property:

(a) There is a deterministic Turing machine which, for any given natural numbers k, m and all 0 lessthan i lessthan (m+1), will output the natural number n on input i if, and only if, F(k, m, n) holds;

(b) There is no deterministic Turing machine which, for any given natural numbers k, m and all 0 lessthan i, will output the natural number n on input i if, and only if, F(k, m, n) holds.

In other words, it follows from the instantiational nature of the constructive definition of the Goedel Beta-function that a primitive recursive relation can be instantiationally equivalent to an arithmetical relation where the former is algorithmically decidable over the structure N of the natural numbers, whilst the latter is algorithmically verifiable, but not algorithmically decidable, over N.

Ergo, P != NP.

Of course there is a caveat: we may need to assume that the standard interpretation of PA is sound.

Moreover, this argument cannot be formalised in ZF since functions and relations are defined extensionally as mappings. Hence ZF cannot recognise that a primitive recursive relation may be instantiationally equivalent to, but computationally different from, an arithmetical relation; where the former is algorithmically decidable over N whilst the latter is instantiationally decidable, but not algorithmically decidable, over

]]>(a) There is a deterministic Turing machine which, for any given natural numbers k, m and all 0

]]>Perhaps the lack of proof is because the focus on “polynomial time” is misleading; what one really needs to ask is whether there is a NP-complete problem that is not “algorithmically computable”.

Let me explain.

The general consensus is that the roots of the PvNP problem trace back to Goedel’s ‘lost’ letter to von Neumann.

However, has anyone seriously considered whether the solution of the PvNP problem can also be traced back to Goedel – in particulkar to Theorem VII of his seminal 1931 paper on undecidable arithmetical propositions?

In the proof of this Theorem (every recursive relation is arithmetical), Goedel introduces an intriguing function, named after him as the Goedel Beta-function.

Goedel uses this to show that, for any recursive relation of the form x0 = f(x1, …, xn) defined by the Recursion Rule, we can define an arithmetical relation F(x1, x2, x3) such that:

(i) if f(k1, …, kn) = k(n+1) then PA proves: [F(k1, …, kn, k(n+1))];

(ii) PA proves: [(E1 x(n+1))F(k1, …, kn, x(n+1))].

(where the symbol `[E1]’ denotes existential uniqueness; and the square brackets are used to denote the PA-formula which interprets as the arithmetical relation that is denoted by the expression inside the brackets under a sound interpretation of PA.)

Now, it is implicit in Goedel’s definition that F(x1, x2, x3) has the property:

(a) There is a deterministic Turing machine which, for any given natural numbers k, m and all 0

]]>Scott’s article about BQP vs PH was really interesting though I couldn’t understand it much. It reminded me of another topic I couldn’t understand, Valiant’s holographic algorithms. So I figure the topics must be related ;). Does anyone know if there has been any attempt to “port” quantum algorithms to the (classical) holographic framework? And are there probabilistic holographic algorithms? The little reading I’ve done only describes deterministic ones.

]]>