Re: infinity

stephen@xxxxxxxxxx said:
> Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> > stephen@xxxxxxxxxx said:
> >> Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> >> > If the word length is finite, then the language is also finite. For any finite
> >> > x, being the length of the longest word in the language, and any finite
> >> > alphabet size y, one can produce no more than y^x words in the language, which
> >> > is a finite number.
> >>
> >> Why are you assuming that there is a longest word in the language?
> >> Once again you are assuming a largest finite natural number,
> >> although of course you will deny it.
> > Why are you assuming the longest words are finite? When you say all words are
> > finite, that means none are infinite, therefore S^L is not infinite either.
>
> I am not assuming that there is a longest word. A longest word
> implies a largest natural number. You always deny that there
> is a largest natural number, but once again you are using an
> argument that depends on there being a largest natural number.
I said "longest WORDS", not "longest word".
>
> I have no idea what L is in your S^L. You are aware that there
> is more than one string length, so picking a single L does not
> make any sense. It almost makes sense if you think that L is
> the maximum string length, i.e. the largest finite natural number.
> Of course you also deny that there is a maximum string
> length, so I have no idea what S^L is supposed to mean.
Given any string length and alphabet, that is the maximum number of unique
srings in the language.
>
> You should have a summation:
> S^0 + S^1 + S^2 + S^3 + .... S^k + ...
> for all finite k. That is the number of finite length strings
> over an alphabet with size S.
Yes, and you are summing a finite number of terms, each of which is finite in
value. Is the sum infinite? No.
>
> You claim that the above summation is finite. According to you
>
> F = sum S^k for all finite k
>
> is a finite number.
That is correct.

> However if F is a finite number, then
> there are strings of length F, and there are S^F strings
> of length F, which is greater than F, the supposed number
> of finite strings. That's a contradiction. Therefore
> F cannot possibly be a finite number.
Darryl just gave a similar "proof". When you say "for all finite k" then you
are saying there is some upper bound to k. k cannot be infinite. Therefore sum
(x=1->k: S^x) is finite. If we use an S-based digital number system, then each
digit represents a power of S, and we get sum(x=1->k:S^x) is a string of k 1's.
Now, how many 1's must we concatenate to get an infinite value? We need an
infinite number of 1's to get an infinite value, with a finite based digital
number system. So, in order to make this sum infinite, k must be infinite,
which means you have infinitely long strings. QED.
>
> >>
> >> There is no longest word in the set of finite words over
> >> the alphabet {0,1}, just as there is not largest finite
> >> number. If you give me a word with L symbols, I can
> >> construct a word with L+1 symbols by appending or prepending
> >> a 0 or 1.
> > No kidding. But all words are finite, you say, because you can define a word
> > which is longer and yet finite?
>
> All the words are finite because if you take a finite string
> and add a finite number of symbols you still get a finite string.
> Remember, you swear up and down that there do not exist finite
> numbers n and k such that n+k is not finite.
Yes, but if either n or k is infinite, then n+k can be infinite. If you add one
character at a time, an infinite number of times, then you have added an
infinite number of characters.
>
> > Well, for any language you can define on these
> > finite words, I can define a larger language simply by adding this L+1 length
> > word, so in the very same sense, the language is finite as well. If the
> > language is infinite because there is no upper obund, then the word length is
> > infinite for the same reason.
>
> What was that supposed to mean? You seem to be saying that
> because you can create a larger language, the original language
> could not be infinite? You are really making less and less sense.
That was in response to your similar statement. Here, now, you say, "All the
words are finite because if you take a finite string and add a finite number of
symbols you still get a finite string." So, in response, I say, "All the
languages are finite because if you take a finite language and add a finite
number of strings you still get a finite language." This directly applies to
your summation of subsets with variable L, above. Can you keep adding finite
sets of strings to a finite set of strings, and get an infinite set of strings?
>
> The set of all finite length strings over the alphabet {0,1}
> is an infinite set. There is no longest string in this
> set, and there is no L to plug into your S^L formula.
If the string length cannot be infinite, then the language cannot be infinite.
>
> That set is finite because there there is no finite bound
> on the number of elements in the set.

I assume you mean infinite. Is there a finite bound on the length of strings in
the set? What is the upper bound for string length?

<QD accusation snipped>
> Stephen
>

--
Smiles,

Tony
.

Relevant Pages

  • Re: infinity
    ... >>> If the word length is finite, then the language is also finite. ... >>> x, being the length of the longest word in the language, and any finite ... > finite, that means none are infinite, therefore S^L is not infinite either. ... the maximum string length, i.e. the largest finite natural number. ...
    (sci.math)
  • Re: infinity
    ... >>> If the word length HAS AN UPPER BOUND, ... and I am not saying that a finite language is necessarily small. ... >> if the string length is strictly finite, ... Sounds infinite to me, this string elongation process, eh? ...
    (sci.math)
  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... > A decidable or recursive language is a formal language that is a recursive ... > YES/NO answer for any input string after a finite amount of time. ... Consider what happens if x is an infinite ... There is only a finite number of naturals ...
    (comp.theory)
  • Re: The longest word
    ... Your language is not easy to understand, but I think you want to find ... the longest word in a string. ... You can split it into its parts (not having Python a built-in lazy ... If you instead want to find the position of the longest word the ...
    (comp.lang.python)
  • Re: The longest word
    ... Your language is not easy to understand, but I think you want to find ... the longest word in a string. ... You can split it into its parts (not having Python a built-in lazy ... If you instead want to find the position of the longest word the ...
    (comp.lang.python)
Loading