super-Turing systems

[AC1MPS@primea.sheffield.ac.uk]

Two points:

(1) All this chat about limericks is irrelevant to the actual purpose
    of this network, as I understand it. Some subscribers have to pay
    to receive this stuff - others have better things to do with their
    time than wade through it all to find the bits that matter. Please
    stop it.

(2) super-Turing systems
    ====================

    For some time now I've been interested in identifying systems that
seem to possess 'super-Turing' potential, in the sense that they can
implement/model processes which are provably not modellable by a Turing
machine program. A few weeks ago, the Pour-El work was broadcast, showing
that some aspects of analog computation were super-Turing. Other examples
exist as well.

    Does anyone know of any others, besides the ones listed below?

    a) Pour-El et al (cited in earlier broadcast)
       The wave equation with computable initial conditions can assume
       non-computable values after computable time.

    b) Myhill (cited in Pour-El's work)
       A recursive function can have non-recursive derivative.

    c) An analog version of the Turing machine can solve the Turing halting
       problem. (myself: "X-machines and the Halting Problem ... ", to
       appear in Formal Aspects of Computing 1990(4)).

    d) An extended version of the universal quantum computer (Deutsch 1985)
       can implement unbounded non-determinism. (myself: work in progress,
       unpublished)  [Reference to Deutsch's work: "Quantum theory, the
       Church-Turing principle, and the universal quantum computer", Proc
       R.Soc.London A400 (1985) pp. 97-117].

    e) Standard concurrency specification languages can represent
       unbounded non-determinism (e.g. CCS using infinite summation).

    f) Smolin/Bennett
       Quantum mechanics can be used in cryptology. Claimed in Deutsch
       1989 (Quantum communication thwarts eavesdroppers, in New
       Scientist, December 9th 1989) that their QPKD system is the
       first physical information processing device with capabilities
       beyond those of the Turing machine.

I'm currently trying to decide how (if?) these models can be unified,
and whether any of them might reasonably be implemented within
biological systems. Is anyone working on similar problems?

Mike Stannett,
AC1MPS @ uk.ac.shefpa