Further reading matter.

[zotz]

Yesterday there was a Guardian article about the philosopher (and sculptor, and jazz pianist, and sailor, and cidermaker . . .) Dan Dennett, who it turns out is a man too talented to be allowed to live. I have recommended his work to some of you before - especially Consciousness Explained and Darwin's dangerous Idea.

Comments

[ciphergoth.livejournal.com]

It's more usual to think of yes/no questions than computing infinite streams; in this case the error bound is a bound on the probability that the machine gets the answer wrong. You can convert an "infinite stream" problem to a "yes/no" problem with a question like "Is bit n of (say) pi 1?". By this definition, most irrationals are not even computable within bounded error.

If you don't know the proof of equivalence between a TM and an NDTM, you should look it up in any undergraduate text on the subject. The reduction is simple: given an NDTM to solve a given problem, evaluate all possible branches simultaneously. If any of them accept, then accept, otherwise don't accept. Just asked a colleague to recommend a suitable textbook, he suggests Michael Sipser, Introduction to the Theory of Computation, or a couple of others I'll add later.

The Church-Turing thesis can't be stated with enough formality to be mathematically proven. What we can do is think of lots of machines that fit the criteria they lay out, and prove that they are simulable on a TM, and that we've done many times. See Wikipedia: Church-Turing Thesis: "...the thesis does not have the status of a theorem and cannot be proven..."

[steer.livejournal.com]

[Error: Irreparable invalid markup ('<em [...] error.</em>') in entry. Owner must fix manually. Raw contents below.]

<em most irrationals are not even computable within bounded error.</em>

Interesting - something I should read more on.

<Em>If you don't know the proof of equivalence between a TM and an NDTM</em>

Apologies - you are correct here. What I was trying to get across was the concept of a Probabilistic Turing machine with an energy minimisation principle factored into to the probabilities. I had (erroneously) thought that an NDTM was the same sort of thing. [I made the same error in a reply to zotz.]

Sidenote: Irksomely, some web references say an NDTM is the same thing as a Quantum Turing Machine and other say this is a common fallacy. I shall give up investigating this on the web and do some work.

[ciphergoth.livejournal.com]

It's a common fallacy. QC is believed to be a different computational class from NP.

[steer.livejournal.com]

But still an open research question I presume [I managed to find web references saying with assurance that NP was solvable in polynomial time using QC and that it certainly was not. Ah, the web, you can find any answer you want there.]

Thanks for the discussion - very interesting, helped me clarify my ideas and I found a few more things to read up on. [If you do ever have a chance to look at that paper I'd be interested on your thoughts as to whether it's lunacy or genius. Haven't studied QM since I was an undergraduate.]

[ciphergoth.livejournal.com]

It is indeed open: we still don't even know if P=NP.

However if you remove the time bounds then all these machines are equivalent.

Here's what my colleague recommended:

[ciphergoth.livejournal.com]

Introductions to computability theory; most of these contain some (basic) material on complexity as well --except Davis:

(1) Hopcroft, J., Ullman, J. & R. Motwani: Introduction to Automata Theory, Languages, and Computation 2/E

Sadly, far less authoritative and complete than the first edition, although more up to date and more accessible to undergrads. Still a good intro, though.

(2) Sipser, M.: Introduction to the Theory of Computation.

Very, very clear and accessible, yet contains non-trivial proofs. Far from complete in coverage, but IMO the best starting point to obtain good intuitions regarding computability and complexity.

(3) Lewis, H. and C. Papadimitriou: Elements of the Theory of Computation

More coverage than Sipser regarding automata and languages, but less on complexity. A sound introduction, if a bit dry.

(4) Davis, Martin: Computability and Unsolvability.

Classic text on computability (*not* complexity). Available in an affordable Dover edition :-)

Personally, I'd go with Sipser as an interesting, accessible introduction to both computability and complexity. However, coverage is selective, so it is certainly not a reference book. Lewis and Papadimitriou is solid, but dry (comparable to trying to eat three Weetabix straight from the packet).

Hopcroft and Ullman is probably the best bet overall. Unfortunately, the second edition doesn' t live up to the first: for a lot of basic results, the first edition is still a better reference, and may be worth tracking down at a college library. It's quite pricey, though. If you're not interested in complexity, then Davis' book is quite complete (and cheap!).

Rgds,

J.

Re: Here's what my colleague recommended:

[steer.livejournal.com]

(Grin) Thanks to the elegant minimalism of York Uni library this decision was made a lot easier. I now have a copy of Hopcroft on loan. Thanks for the info.

[ciphergoth.livejournal.com]

What I was trying to get across was the concept of a Probabilistic Turing machine with an energy minimisation principle factored into to the probabilities.

Not sure exactly what you mean here; if you mean a quantum Turing Machine (ie one in which the probability of a particular result is determined by a sum of amplitudes) then that too is equivalent to a TM. Or if you mean something where each result has a weight and the one with the least weight wins, then that's equivalent too (so long as you work out the details in a reasonable way and don't try and slip in the ability to do infinite work in finite time).

[steer.livejournal.com]

I guess I'm thinking aloud here so perhaps should stop -- the sort of consideration I'm thinking of is the way which QM systems can find a base energy from a variety of answers -- e.g. not only calculate a number of sums in parallel but select the one which is in some sense optimal. However, I'm afraid at this point my recollection of QM has grown amazingly hazy and I'm not sure whether I'm confusing this with other issues so I'd best stop while I'm behind. :-)