msb@link.UUCP (Mike S. Balenger x8789) (03/04/86)
> 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. -- ---------------------------------------------------------------------- <cute quote> Michael S. Balenger (201) 949-8789 <cute disclamer> AT&T Bell Labs Crawfords Corner Road ihnp4!link!msb Holmdel, NJ 07733
ins_ampm@jhunix.UUCP (Michael P McKenna) (03/06/86)
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
rmariani@watnot.UUCP (Rico Mariani) (03/07/86)
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...
mdr@bentley.UUCP (M. Rossner) (03/07/86)
>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. And it is obvious that the set of true sentences is countabe. I need only concatenate together the ASCII codes for each character in the sentence to come up with a unique positive integer for that sentence. If the sentences are identical, the integers will be identical; if the integers are identical, the sentences must have been the same. Thus the number of sentences (not even necessarily true) is countably infinite, as is the number of computer programs, books, musical scores (using Western notation), or any other printed matter. Marc D. Rossner AT&T Bell Labs, Liberty Corner
ins_ampm@jhunix.UUCP (Michael P McKenna) (03/09/86)
In article <616@bentley.UUCP> mdr@bentley.UUCP writes: > >>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. > > >And it is obvious that the set of true sentences is countabe. I need >only concatenate together the ASCII codes for each character in the >sentence to come up with a unique positive integer for that sentence. >If the sentences are identical, the integers will be identical; if the >integers are identical, the sentences must have been the same. Thus the >number of sentences (not even necessarily true) is countably infinite, >as is the number of computer programs, books, musical scores (using >Western notation), or any other printed matter. > This is obvious if we take the traditional view that sentences are finite in length. What if we extend the idea of a sentence to include such things as: The sentence, "The sentence, "The sentence, ... is true." is true." is true. or worse yet The sentence, "The sentence, "The sentence, ... is false." is false." is false. or from Martin Gardner's article on Mobius Bands in _Mathematical Magic Show_ Once upon a time there was a story that began, "Once upon a time was a story that began, "Once upon a time..." and a LONG poem... One day A mad metapoet With little to say Wrote a mad metapoem That started: "One day A mad metapoet With little to say Wrote a mad metapoem That started: "One day . . . Sort of a close," Were the words that the poet Finally chose To bring his mad poem To some Sort of a close," Were the words that the poet Finally chose To bring his mad poem To some Sort of close. Actually we can use a variation of the mapping above to show that the number of sentences similar to these is countable. We have two types of sentences here, sentences like the third example and sentences like the other three. Sentences like the third example consist of a phrase that infinitely repeated. Simply construct the real number formed by placing the appending the ASCII numbers of each letter after a decimal point. This forms a repeating decimal, which is of course a rational number. The other sentences consist of two blocks, the first block is infinitely repeated THEN the second block is infinitely repeated. We shall form a repeating decimal in this manner. Start with a decimal point. Append the ASCII code of the first character in the first block, then the first character in the second block, then the second character in the first block, second in second block, etc. If one block is longer than the other just append all the characters left when the shorter block is exhausted, repeat until bored. This is clearly a repeating decimal. This method clearly extends to any finite number of blocks. Note that you can't mix the mappings, each mapping proves that a certain set of sentences is countable, therefore the union of these sets (so far a countable number of sets), is countable. What would be more interesting would be to see a sentence that maps to an irrational number using one of the above methods. This can clearly be done by stringing random words together, but we really want some sort of meaning in the sentences (at least as much as in the examples above). Another method would be to string variations of the phrase "Once upon a time there was a story that began" together at random. Ideally we want some rule for telling what the next phrase is. (For example the number .101001000100001000001... is irrational and the generation method is obvious). Of course generating such sentences does not prove the uncountability of the set of extended sentences, for there may be some other mapping that would map them to rational numbers. Anyway this is digressing from the original puzzle and is getting quite long so I'll quit. It would be nice to see some "irrational sentences" posted though. Dwight S. Wilson
ags@pucc-h (Dave Seaman) (03/12/86)
In article <11581@watnot.UUCP> rmariani@watnot.UUCP (Rico Mariani) writes: >It is possible for a machine to generate a countably infinite number >of truths in a finite amount of time. True, if you allow the machine to run infinitely fast, but in computability theory it is the finiteness or non-finiteness of the number of operations that is significant. References to "time" are merely a linguistic convenience based on the assumption that the machine runs at a uniform finite rate. >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). Very well, I will grant you BOTH an infinite (countable) alphabet and sentences of "arbitrary" (i.e. finite) length. The number of sentences is still countable. This does mean we cannot make statements about arbitrary real numbers (only countably many numbers can be "named"), but that is not news. Obviously one can speak of infinite sequences of characters, but I see no justification for calling these "sentences." A "sentence" is a sequence of symbols which can be parsed according to the rules of some language. Any language which can be expressed in EBNF form has sentences of finite length only. -- Dave Seaman pur-ee!pucc-h!ags
mmar@sphinx.UChicago.UUCP (Mitchell Marks) (03/14/86)
You can also get sentences of unbounded length this comparatively
easy way:
John is very tired.
john is very very tired.
John is very very very tired.
John is very very very very tired.
...
--
-- Mitch Marks @ UChicago
...ihnp4!gargoyle!sphinx!mmarmmar@sphinx.UChicago.UUCP (Mitchell Marks) (03/14/86)
In article <2694@pucc-h> ags@pucc-h.UUCP (Dave Seaman) writes: >Obviously one can speak of infinite sequences of characters, but I see no >justification for calling these "sentences." A "sentence" is a sequence of >symbols which can be parsed according to the rules of some language. Any >language which can be expressed in EBNF form has sentences of finite length >only. >-- >Dave Seaman pur-ee!pucc-h!ags I don't see that. Consider the "john is very ... very tired" sequence from my previous posting. Here's a CFG (equivalent to BNF) for a similar language: S --> Dave is wrong. S --> Dave is <VERYSTRING> wrong. VERYSTRING --> very VERYSTRING --> <VERYSTRING> very Or perhaps he's right, if he just means that any particular sentence is of finite length. But as long as that length is unbounded, you still haven't guaranteed a countable language. Here's another grammar: S --> aS S --> bS S --> a S --> b The language is any nonempty string of a and b. Any particular sentence is finite, but the language is ripe for a diagonal argument showing that it's uncountable. Readers for whom the construction is obvious, please skip to end. Give me a putative mapping from the natural numbers to the sentences of this language, and I construct a sentence which differs from your sentence #1 in place #1, differs from your #2 in place #2, etc, yet which accords with the grammar. This is easy to do: if your sentence #n has length n or greater, I pick the other character at position #n; if your sentence #n is shorter than n characters, I freely pick a or b. My sentence is a nonempty string of a and b, so it's in the language. Is it on your list? You have it as #1307? No, it differs in position #1307. -- -- Mitch Marks @ UChicago ...ihnp4!gargoyle!sphinx!mmar
steve@anasazi.UUCP (Steve Villee) (03/19/86)
> Or perhaps he's right, if he just means that any particular sentence > is of finite length. But as long as that length is unbounded, you > still haven't guaranteed a countable language. Here's another grammar: > > S --> aS > S --> bS > S --> a > S --> b > > The language is any nonempty string of a and b. Any particular sentence > is finite, but the language is ripe for a diagonal argument showing that > it's uncountable. Readers for whom the construction is obvious, > please skip to end. > Give me a putative mapping from the natural numbers > to the sentences of this language, and I construct a sentence which differs > from your sentence #1 in place #1, differs from your #2 in place #2, etc, > yet which accords with the grammar. This is easy to do: if your sentence > #n has length n or greater, I pick the other character at position #n; if > your sentence #n is shorter than n characters, I freely pick a or b. My > sentence is a nonempty string of a and b, so it's in the language. Is it > on your list? You have it as #1307? No, it differs in position #1307. > -- > > -- Mitch Marks @ UChicago > ...ihnp4!gargoyle!sphinx!mmar I think this argument is faulty, and that the set of sentences in the above language is in fact countable. One obvious bijection from the natural numbers to this set is as follows. For each natural number n, represent n+1 in base 2. The first (i.e. most significant) digit will be a 1. Discard this digit. For the remaining digits, substitute a for 0 and b for 1. You now have the sentence to be associated with the number n. This is assuming 0 is not a natural number; many mathematicians include 0, in which case you need to represent n+2 in base 2 instead of n+1. Mitch attempts to construct a sentence which is not associated with any natural number under my mapping. However, if I am reading correctly, his sentence is not of finite length. Of course, if the language includes infinitely long strings of a and b, then the set is not countable. --- Steve Villee (ihnp4!terak!anasazi!steve) International Anasazi, Inc. 7500 North Dreamy Draw Drive, Suite 120 Phoenix, Arizona 85020 (602) 870-3330