Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watnot.UUCP
Path: utzoo!watmath!watnot!rmariani
From: rmariani@watnot.UUCP (Rico Mariani)
Newsgroups: net.puzzle
Subject: Re: truth machine clarification**2
Message-ID: <11581@watnot.UUCP>
Date: Fri, 7-Mar-86 11:02:33 EST
Article-I.D.: watnot.11581
Posted: Fri Mar  7 11:02:33 1986
Date-Received: Sat, 8-Mar-86 05:27:52 EST
References: <423@watdragon.UUCP> <2664@pucc-h> <394@link.UUCP> <2109@jhunix.UUCP>
Reply-To: rmariani@watnot.UUCP (Rico Mariani)
Organization: U of Waterloo, Ontario
Lines: 52
Summary: 

In article <2109@jhunix.UUCP> ins_ampm@jhunix.ARPA (Michael P McKenna) writes:
>In article <394@link.UUCP> msb@link.UUCP writes:
>>>In article <423@watdragon.UUCP> gawilson@watdragon.UUCP (Graham Wilson) writes:
>>>>Consider a machine which is used to create true sentences (for example,
>>>>the sentence "A dog is a dog" is true).  If the machine is "complete",
>>>>then it could, given time, produce the set of ALL true sentences.  If the
>>>		^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>>>machine is "consistent", then all the sentences that it produces will be
>>>>true.
>>>>
>>>>Question:  Can such a machine exist (even in theory)?
>>> 
>>>The machine cannot produce the set of ALL true sentences unless that set
>>>is finite.  I think you meant to say any given true sentence would eventually
>>>be produced by the machine.
>>>-- 
>>>Dave Seaman	  					pur-ee!pucc-h!ags
>>
>>You can't even guarantee that any given true sentence would eventually be
>>produced by the machine unless the set is finite.
>
>You mean countable.  If the set is countable there exists a 1 to 1
>correspondence with the set of positive integers.  Thus each true
>statement can be associated with a unique integer.  We need only
>specify that the machine produces the statements in this order to
>guarantee that any true statement is eventually produced.
>
>                                                        Dwight S. Wilson

Point of information:

It is possible for a machine to generate a countably infinite number
of truths in a finite amount of time.  Suppose that the machine generates
the 1st truth in 1 second, the second in 1/2 a second, the next in 1/4
and so on.  After 2 seconds have elapsed, ALL of the truths in a countably
infinite set will have been generated.

Dave Seaman made a comment about the number of true sentences over a finite
alphabet being necessarily countable, this is true if you assume that all
sentences are of finite length however this is not such a reasonable 
assumption to make (we can't make statements about arbitrary real numbers
unless we either allow an infinite alphabet or sentences of arbitrary
length).

Then again,  I don't know what I'm talking about anyway.

	-Rico

	 {allegra|linus|decvax|ihnp4|utzoo}!watmath!watnot!rmariani

It's funny that this countability argument came out of a problem which
was supposed get us thinking about Incompleteness and such...