- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Fri, 7 Feb 2003 08:58:55 +0100

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 his
*

*>papers. How do we balance the notion of the universality of computation
*

*>against this notion? It seems to me that the notion of universality implies,
*

*>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 theory
*

*>of Malament-Hogarth machines in which it was pointed out that there does not
*

*>exist a universality property for them. Would the notion, of intelligence,
*

*>that you seem to imply below be more applicable to such rather than machines
*

*>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 there
*

*>exist a notion of computation that would involve functions C -> C, where C
*

*>is the "space" of complex numbers, analogous to the notion of Church-Turing
*

*>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 read

a Los Alamos "quant-phys" suggesting to found quantum computing on

a similar ring-generalization. All those approach subsumes the (classical)

Church Thesis.

Bruno

Received on Fri Feb 07 2003 - 02:59:21 PST

Date: Fri, 7 Feb 2003 08:58:55 +0100

Stephen Paul King wrote (in the FOR list):

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.

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.

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 read

a Los Alamos "quant-phys" suggesting to found quantum computing on

a similar ring-generalization. All those approach subsumes the (classical)

Church Thesis.

Bruno

Received on Fri Feb 07 2003 - 02:59:21 PST

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