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

From: <hal.domain.name.hidden>

Date: Fri, 29 Jan 1999 08:54:30 -0800

Wei Dai wrote, responding to a suggestion by Jacques Mallah:

*>That is not the model I have in mind. It doesn't seem sensible to think of
*

*>a universe with a continuous infinity of Turing machines. Instead I assume
*

*>that the universe starts with one Turing machine with a blank (read-only)
*

*>input tape, then before each clock cycle each existing Turing machine is
*

*>cloned, with 0 appended to the input tape of one copy, and 1 appended to
*

*>the input tape of the other.
*

[He later changed his mind and said that perhaps you could have a continuous

infinity of Turing machines.]

Maybe you could have a continuous infinity of Turing machines, but I'm not

sure you could have a continuous infinity of Turing machine *programs*.

It would depend on whether it made sense to have an infinitely long

program. If we required legal programs to have some kind of syntax, say

a balanced number of parentheses, or some kind of end symbol (which is the

approach adopted by Greg Chaitin in his considerations of similar issues)

then any syntactically legal program would be finite. I don't believe

this impairs the universality of the TM by the standard definitions.

If all TM programs must be finite, then there can be only a countable

infinity of programs. If we allow the notion of an infinitely long (and

infinitely complex) computer program, then there would be an uncountable

infinity of them.

Which of these views seems correct?

Hal

Received on Fri Jan 29 1999 - 09:39:59 PST

Date: Fri, 29 Jan 1999 08:54:30 -0800

Wei Dai wrote, responding to a suggestion by Jacques Mallah:

[He later changed his mind and said that perhaps you could have a continuous

infinity of Turing machines.]

Maybe you could have a continuous infinity of Turing machines, but I'm not

sure you could have a continuous infinity of Turing machine *programs*.

It would depend on whether it made sense to have an infinitely long

program. If we required legal programs to have some kind of syntax, say

a balanced number of parentheses, or some kind of end symbol (which is the

approach adopted by Greg Chaitin in his considerations of similar issues)

then any syntactically legal program would be finite. I don't believe

this impairs the universality of the TM by the standard definitions.

If all TM programs must be finite, then there can be only a countable

infinity of programs. If we allow the notion of an infinitely long (and

infinitely complex) computer program, then there would be an uncountable

infinity of them.

Which of these views seems correct?

Hal

Received on Fri Jan 29 1999 - 09:39:59 PST

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