Infinite computing: A paper

From: Stephen Paul King <>
Date: Sun, 9 Feb 2003 19:54:40 -0500

Dear Bruno and Friends,

    Let me point this paper as a possible counterexample to your argument:

Quantum Physics, abstract
From: Tien D. Kieu <>
Date (v1): Thu, 16 May 2002 12:10:57 GMT (28kb)
Date (revised v2): Mon, 18 Nov 2002 04:26:38 GMT (38kb)

Quantum Principles and Mathematical Computability
Authors: Tien D Kieu
Comments: 9 pages in A4 size and 10pt fonts, 3 figures. Modified with a new
reference added for submission to QS2002

  Taking the view that computation is after all physical, we argue that
physics, particularly quantum physics, could help extend the notion of
computability. Here, we list the important and unique features of quantum
mechanics and then outline a quantum mechanical "algorithm" for one of the
insoluble problems of mathematics, the Hilbert's tenth and equivalently the
Turing halting problem. The key element of this algorithm is the {\em
computability} and {\em measurability} of both the values of physical
observables and of the quantum-mechanical probability distributions for
these values.

Kindest regards,


----- Original Message -----
From: "Bruno Marchal" <>
To: <>
Cc: <>
Sent: Friday, February 07, 2003 2:58 AM
Subject: Re: Persons

> Stephen Paul King wrote (in the FOR list):
> > The notion of "intelligence" that you mention below seems very close to
> >the notion of "expressiveness" that Peter Wegner develops in several of
> >papers. How do we balance the notion of the universality of computation
> >against this notion? It seems to me that the notion of universality
> >at least for Church-Turing machines, that they are all equally expressive
> >since, if we neglect the number of steps the machines take, any one
> >universal computer can perform exactly the same computation as any other.
> It has been shown by Putnam that there is no "perfect" universal learning
> machine, that is, machine capable to identify in a finite time any total
> (everywhere defined on N) function.
> If you allow a learning machine to change its mind infinitely often (that
> is to change his explanation (program) when he get more big sample of the
> function it tries to identify) AND if you allow a finite but unbounded
> number of mistakes in the explanation, then, at least in principle, there
> is a universal learning machine.
> > As a side note, I have read a paper discussing the computational
> >of Malament-Hogarth machines in which it was pointed out that there does
> >exist a universality property for them. Would the notion, of
> >that you seem to imply below be more applicable to such rather than
> >defined by the Church-Turing thesis?
> I don't think so. Malament-Hogart Machines are abstract *computer* having
> some infinite capacities (if I remember correctly). Learning machine are
> just any computer programmed to generate explanation (in the form of
> computer program) when they are given data (sequence of input/output).
> Of course such machine are "stream-interactive" in a Peter Wegner related
> sense.
> >Have you considered more abstract notions of computation that are not
> >limited to those expressible by "physical systems"? For example, could
> >exist a notion of computation that would involve functions C -> C, where
> >is the "space" of complex numbers, analogous to the notion of
> >computations as functions N -> N?
> Blum Shub and Smale have generalize the notion of computer by
> computer on a ring (like R or C). They have prove in this setting
> that the Mandelbrot set is undecidable (answering a conjecture by myself
> and Penrose). From this you can look at the Mandelbrot set as a sort of
> compactified projection of a universal dovetailer.
> Blum & Al. approach to computability gives interesting bridge between
> numerical analysis and classical computability. I remember also having
> a Los Alamos "quant-phys" suggesting to found quantum computing on
> a similar ring-generalization. All those approach subsumes the (classical)
> Church Thesis.
> Bruno
> Your use of Yahoo! Groups is subject to
Received on Sun Feb 09 2003 - 19:58:19 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:08 PST