New Puzzle (honestly...)
Graham Wilson
have not seen this one (or any variations). Credit goes to me (Graham
Wilson) and Peter Fruchter. We originally thought it up as an analogy
to explain Godel's Incompleteness Theorem...
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)?
Note that your answer must involve an iron-clad proof (i.e. like a math
theorem.
Persons who have read "Godel, Escher, Bach, An...." by D.H. should consider
disqualifying themselves.
---------------------------------------------------------------------------
Graham Wilson
University of Waterloo
gawilson@watdragon
Dave Seaman
>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
Mike S. Balenger x8789
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
Michael P McKenna
>> In article <4...@watdragon.UUCP> gawi...@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
Rico Mariani
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...
M. Rossner
>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
Michael P McKenna
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
Dave Seaman
>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
Mitchell Marks
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!mmar
Mitchell Marks
>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.
Steve Villee
> 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