I think the question needs to be cleaned up a bit. In particular, the “uniquely and completely describes every English statement possible” part is iffy. First, this statement is infinite and English statements are finite. Second, this statement specifies that there is the letter “T” at the beginning which is obviously not true for all statements.
Do you want to say that every English statement can be converted to this form?
Somewhere in this text, or in this statement, a pause in self describing is declared and taken, and the next statement is described. Maybe only a part of it, then the selfdescribing is continued.
Do you want to say that every English statement can be converted to this form?
No. I am saying that somewhere inside this mammoth statement every finite English statement is described. Which is maybe possible.
But also, what about those which are not finite, like this one?
That English statement we are referring to, is like a program, an algorithm which writes itself. The first thing which is mentioned is its first letter. Then another and another and entire substrings inside quotation marks. Blanks, commas, periods are also described when need to.
This way, this statement is auto-described.
Beside this, it describes some other English statements too. Like this one, here.
is like a program, an algorithm which writes itself … this statement is auto-described
Sure.
Beside this, it describes some other English statements too. Like this one, here.
Why?
If it’s an algorithm that generates text describing its own preceding text, I see no reason for it to generate e.g. “Beside this, it describes some other English statements too.”
Or let’s make it simpler. Take a word, say “xyzzy”. Why would this algorithm ever generate this word?
But that does not change much. You may have any finite number of additional words. You can erase “cwm” from the vocabulary if you want, the problem is the same.
Can you describe all sentences in an infinite, auto describing sentence?
You may have any finite number of additional words.
The difficulty is not simply that the vocabulary is not perfectly well defined; it’s that “English” really means, in practice, something like “whatever someone considered an English speaker finds themselves able to understand as English” and yes, that’s circular. Languages evolve, writers deliberately push the boundaries, etc. Is the property of being English even computable? Probably (though I wouldn’t want my life or my job to depend on being able to provide even a sketchy proof) for finite sentences; for the infinite “sentences” you want to allow, though, not so much. It’s not even clear what “computable” would mean there; it certainly can’t be anything that involves feeding the “sentence” to a machine that does a finite amount of computation and then returns a verdict.
I wonder whether we’re at cross purposes. I think you’re arguing that English is Turing-complete in the sense that you can describe in English any computational process you please; the question I posed was sort of dual to that, namely whether English is computable in the sense that there exists a computer program that perfectly distinguishes valid English sentences from everything else.
I think the boundaries of “valid English sentences” are fuzzy, which already makes that problematic. Otherwise, if we nail down the definition of “English” to something like “agreed by a majority of fluent English-speakers in April 2017 to be valid English” then the answer is probably yes because we can “just” simulate all those fluent English-speakers.
But, again, all that applies only to finite sentences. You want to allow infinitely long “sentences” too, and that opens up a whole lot of other cans of worms.
Ah, that explains a thing or two. You’re not trying (or at least not trying very hard) to make what you say make sense because you want it not to make sense, “to discredit”, and you don’t expect it to make sense because you’re using concepts you think don’t make sense themselves.
But the actual likely outcome is what’s happening here. No one is saying (and I bet no one is thinking) “this doesn’t entirely make sense—obviously the notion of infinity is problematic” but some people are thinking “huh, Thomas seems either confused or unreasonably unwilling to clarify”.
If you want to discredit something, the first step is to take it seriously.
The not so far away superintelligence will understand. ;-)
I came to the conclusion, that most people love the infinity so deeply and strongly for a reason. Otherwise their spiritual emptiness would be really unbearable. The infinity is a leftover after their abandoned religion, or a pillar of their actual religion.
That’s a nicely unfalsifiable bit of bulverism you’ve got there. I think I agree that “no rational argument would probably do”, but we may not mean the same thing by that.
[EDITED to add: I see no particular problem with the use of infinities in mathematics and never have; back when I was religious, I saw the mathematical notion of infinity as clashing a little with my notion of God—because in mathematics there is e.g. no all-surpassing maximal infinity—and I don’t recall ever, as theist or as atheist, “loving infinity deeply and strongly” or seeing mathematical notions of infinity as doing anything to create or fill “spiritual emptiness”. Of course introspection is unreliable, but it’s all I’ve got :-).]
I was always an non-spiritual atheist. (But I am a non-progressive, too,)
It may seems a bit naive, but when I have heard (as a child) about that paradox about omnipotent god who can’t create a rock so heavy that even he couldn’t lift … then I suddenly “knew” that quantities too big are (logically) problematic. Let alone infinite quantities.
Today, Yablo’s paradox is already good enough for me, to convince me that the infinity doesn’t work. How everybody doesn’t agree with me about this—baffles me.
Infinity is an abstraction that makes thinking about certain problems easier. It’s not a feature of reality (=territory), it’s a tool for thinking (=map). As with any tool, there are contexts where it is very helpful; there are contexts where it is inappropriate; and there are contexts where it can be misused.
Without the concept of infinity you’ll struggle with even basic geometry (consider a line) and calculus becomes an outright impossibility.
Without the concept of infinity you’ll struggle with even basic geometry
No matter, no matter. The fact that this concept of infinity sometimes makes our life easier, doesn’t make everything right about it. Maybe we should try harder. Going the right path isn’t always easy, it can be extremely hard. Perhaps unbelievably hard.
100 years ago, they thought that the self reflection is in the core of paradoxes, like Russell’s and related.
I thought long ago, that the infinity has its share here. With Yablo’s paradox, this is quite obvious. No self-reflection, but still a paradox. But if the Yablo’s list of statements is finite, than the last statement is true (vacuous truth), and—no problemo!
I can’t live with an infinite number of (even all finite) sentences. Because those statements may all be “every higher on this list statement is false”. But that would imply that the next statement is in fact true. Which means that this statement is false. But all saying the same, that would mean it is true. And so on in a circle.
I may have misunderstood your argument Thomas. Are you saying that because it’s possible to construct a paradox ( in this case Yablo’s paradox ) using an infinitude, that the concept of infinity is itself paradoxical?
Couldn’t you make a similar argument about finite systems such as, say?:
A: B is false,
B: A is false
Here are only two sentences. Is the number two therefore paradoxical? I apologize if it sounds like I’m trying to parody your argument—I really would like to learn that I’ve misunderstood it, and in what way.
using an infinitude, that the concept of infinity is itself paradoxical?
I have to admit, that no. Perhaps it is something else wrong here. It might be. Not very likely, but still possible. We see, that finite lists don’t suffer because of Yablo’s paradox, infinite lists do. Still, it may be something else which really causes the A & NOT A situation..
Couldn’t you make a similar argument about finite systems such as, say?:
A: B is false, B: A is false
You can. And you have a contradictory little system here. Which is therefore useless. So you take another one, like the rules for the game of chess. Hoping, that there is no paradox there. (But there is. You can’t believe it, but there is a paradox inside the chess rules!)
In practice, you can continue to play chess and use infinities. But that is at your own risk.
No. Zeno paradoxes aren’t real. Why? You have to have an axiomatic system and inside this system you must be able to prove A & NOT A. Then and only then, there is a paradox.
Then EVERY statement is provable inside this axiomatic system and the system is useless.
Zeno had only “paradoxes”. Had he formulated one of his paradoxes inside geometry, that would be something! But he didn’t. All Zeno had was his intuition that “you can’t do infinite number of steps in a finite time”.
For the Russell’s paradox inside the Naive Set Theory, that is a different story. Using those axioms one can prove that his B is its own member. And one can also prove that it isn’t.
But those Cantor’s examples, like the Infinite Hotel—are NOT paradoxes. It is odd, and “paradoxical” if you wish, but that’s fine. Had Cantor proved, that this hotel can accommodate exactly 7 guests - and someone else (or Cantor) had proved that this hotel can accommodate exactly 12 guests—that would be a paradox indeed.
“you can’t do infinite number of steps in a finite time”
Well, can you? If some finite period must elapse when a finite distance is covered, an an infinite distance is greater than any finite distance, then the period of time elapsed in crossing an infinite segment must be greater than the period that elapses for crossing any finite segment, and thus also infinite.
I suppose you can also assume that you can cross a finite segment without a finite period of time elapsing—but then what’s to prevent any finite segment of arbitrary length being crossed instantaneously?
What seemed the infinite number of steps to Zeno (and pretty much to everybody else), may be only some finite number of Planck’s lengths to cross in some finite number of Planck’s time units.
(In the fifth century A.D., Indian mathematicians reconciled the doubts of Zeno, using infinite series and those solutions officially still hold. If you want to keep the infinitely divisible space and time, you may do it their way.)
He proved, that every system rich enough to contain “infinite arithmetics” is EITHER inconsistent (have paradoxes) EITHER have some non provable sentences.
Almost everybody thought—“Okay, okay, so we’ll always have nonprovables. It’s a shame, but what can we do?”
But this was not the only one explanation. The “Okay, okay so we can’t make the complete “infinite arithmetic” without a paradox. We must cease to even try that.”—flies at least as well.
He proved, that there is ALWAYS either at least one “A & ~A” (and therefore many) - either an unprovable theorem exists. Inside all those systems, which contain the “standard calculus”!
He didn’t prove an actual “A & ~A”, but that one always exists, if there are no unprovable theorems in those “standard calculus systems”.
He proved, that there is ALWAYS either at least one “A & ~A” (and therefore many) - either an unprovable theorem exists. Inside all those systems, which contain the “standard calculus”!
That isn’t actually grammatical English, and unfortunately some plausible guesses at reconstructing it produce things that are completely false. So here’s what Goedel actually he did: he proved that for any powerful enough system either there is at least one (hence many) A & ~A, or there are A for which neither A nor ~A can be proved by the system.
It’s not “almost correct”, it’s actually correct. I wasn’t trying to make it complete :-). Yes, the “powerful enough” criterion is about being able to represent arithmetic. But if you want an actually-complete statement then “with arithmetics” and “contain the ‘standard calculus’” really aren’t any better than “powerful enough”. (I can never remember the exact requirements and am too lazy to look them up for this sort of discussion, and it’s not like the details matter very much here.)
Finite sets of numbers have obvious problems, well explored in computer science (if you integer has be be expressed in 4 bytes, you can express only a finite set of integers. Or real numbers, for that matter).
Trivially, if your finite set ends at n, what is the sum of (n-1) + (n-2)? A plausible answer is “you can’t do that”, but that’s also an answer to any paradox whatsoever.
How do you feel about imaginary numbers, by the way?
A plausible answer is “you can’t do that”, but that’s also an answer to any paradox whatsoever.
No, this is not true. The only answer we have to paradoxes is—change you axiom system!
How do you feel about imaginary numbers, by the way?
There are no paradoxes there. At least no paradoxes which wouldn’t be present in the real numbers already.
SQRT(-1)=i is no paradox whatsoever. People might often say—“oh, well that’s paradoxical”.
No, it’s not. No A & ~ A here. It might be weird to somebody, that you can calculate square roots from negative numbers. I really don’t see why, but it might.
Weirdness and paradoxicality are two different things.
You can eliminate paradoxes by declaring operations which lead to them “illegal”
Precisely! You narrow your axiomatic system, hoping that one of contradictors will fall out. They’ve eliminated self containing sets from the Naive Set Theory and Russell’s paradox vanished. Hopefully.
Is i a number? If not, what is it?
It is not “what is it”, it is “how does it behave”. Whatever behaves as a number, is a number.
Does it have a sign?
If it behaves as it had a sign … And it does. So yes, it has a sign!
It is a sentence from a book written in English (maybe I should say ostensibly in English). Though to be fair the author isn’t English—he is Scottish :-)
In the Silicon Dreams text adventure series (a sci-fi series) if you say “xyzzy” a robot will come up to you and assume that you are insane (since you are trying to cast a magical spell) and transport you to the appropriate place for insane people.
Congratulations to Gurkenglas on guessing what you meant, then. Gg’s understanding differs from what I assumed, in so far as I was able to figure out your meaning, but the actual content of the puzzle was simple enough that I guess the obfuscation was most of the point.
I thought Gurkenglas’ solution was a lovely discrete math sledgehammer approach. There’s a lot of subtly different problems that Thomas could have meant and I think Gurkenglas’ approach would probably be enough to tackle most of them.
(Attempting to summarize his proof: Some English sentences, like the one this problem is asking you to dig around in, are countably infinite in length. If some English sentences are countably infinite in length, and any two of them have different infinite suffixes, then there’s no way the text of this sentence contains both of them.)
I think your summary is wrong, I’m afraid. The sentence could contain two different infinite suffixes—e.g., by interleaving them. (Well, maybe; it still isn’t clear to me what sort of descriptions Thomas is intending to allow.) The problem isn’t that having multiple infinite suffixes is a problem, it’s that (at least for certain rather non-standard notions of what a “sentence” is) there are uncountably many different sentences and if they all have to be described separately you’re dead.
If you allow one description to cover multiple sentences, though, you can cover all those uncountably many with something countably long. Suppose the words of the language are W1, W2, …, Wn and suppose a “sentence” is any string of finitely or countably many of them. (That’s not true for any actual natural language, of course, but this language does have uncountably many “sentences”.) Then you could say: “A sentence consists of the empty string, or: of one of W1,...,Wn followed either by the empty string or by: one of W1,...,Wn followed either by the empty string or by: …...”.
You could also, though this is a further step away from the sort of description I think Thomas wants to allow, do that in finite space. In fact, I already did, earlier in the paragraph above.
I think you’re right. I’m badly overlooking a subtlety because I’m narrowing “describe” down to “is a suffix of.” But you’re right that “describe” can be extended to include a lot of other relationships between parts of the big sentence and little sentences, and you’re also right that this argument doesn’t necessarily apply if you unconstrain “describe” that way. (I haven’t formalized exactly what you can constrain “describe” to mean—only that there are definitions that obviously make our sledgehammer argument break.)
I think “a sentence can be countably infinite” is implicit from the problem description because the problem implies that our “giant block of descriptions” sentence probably has countably infinite size. (it can’t exactly be uncountably infinite)
One of the problems was that Thomas spoke about a “natural language” that we all know what it looks like. And a natural language does not have infinite-length sentences.
Another is that Thomas’s question didn’t make it clear that each sentence covered had to be called out individually, as opposed to constructing some description that covers exactly the right sentences. Another is that even if we suppose our natural language augmented by allowing infinite sentences, it’s not clear that it should allow non-computable infinite sentences.
It’s so defined, that it can explicitly describes any meaningful sentence in English.
So what is this definition?
As far as I can see, your algorithm starts with a specific statement and then basically recurses forever creating the “mammoth statement”. But if you start with a different statement, you’ll get a different “mammoth statement”. And I still don’t see how one single “mammoth statement” will describe any meaningful sentence (and why the constraint on meaningful? meaningful to whom?)
I think the question needs to be cleaned up a bit. In particular, the “uniquely and completely describes every English statement possible” part is iffy. First, this statement is infinite and English statements are finite. Second, this statement specifies that there is the letter “T” at the beginning which is obviously not true for all statements.
Do you want to say that every English statement can be converted to this form?
Somewhere in this text, or in this statement, a pause in self describing is declared and taken, and the next statement is described. Maybe only a part of it, then the selfdescribing is continued.
No. I am saying that somewhere inside this mammoth statement every finite English statement is described. Which is maybe possible.
But also, what about those which are not finite, like this one?
So it’s a nested structure?
Where is this “next statement” coming from?
If this statement is generating them itself you need to get more specific about the rules according to which it operates.
I will try.
That English statement we are referring to, is like a program, an algorithm which writes itself. The first thing which is mentioned is its first letter. Then another and another and entire substrings inside quotation marks. Blanks, commas, periods are also described when need to.
This way, this statement is auto-described.
Beside this, it describes some other English statements too. Like this one, here.
Okay, so far?
Sure.
Why?
If it’s an algorithm that generates text describing its own preceding text, I see no reason for it to generate e.g. “Beside this, it describes some other English statements too.”
Or let’s make it simpler. Take a word, say “xyzzy”. Why would this algorithm ever generate this word?
It does that, but not exclusively.
So define your algorithm, then.
It just talk and talk about everything you can imagine. Every now and then it describes its more and more distant beginning.
That’s not a algorithm about which you can ask questions and receive well-defined answers.
We all know what a natural language, like English is. And how a text in such a language looks like.
And how it can describe itself, letter by letter, for example.
Oh, do we now? Let’s try.
Is this a natural language, English, maybe?
Oi! Stop giving away endings.
It is not English. Perhaps it is Inglish.
But that does not change much. You may have any finite number of additional words. You can erase “cwm” from the vocabulary if you want, the problem is the same.
Can you describe all sentences in an infinite, auto describing sentence?
The difficulty is not simply that the vocabulary is not perfectly well defined; it’s that “English” really means, in practice, something like “whatever someone considered an English speaker finds themselves able to understand as English” and yes, that’s circular. Languages evolve, writers deliberately push the boundaries, etc. Is the property of being English even computable? Probably (though I wouldn’t want my life or my job to depend on being able to provide even a sketchy proof) for finite sentences; for the infinite “sentences” you want to allow, though, not so much. It’s not even clear what “computable” would mean there; it certainly can’t be anything that involves feeding the “sentence” to a machine that does a finite amount of computation and then returns a verdict.
English is computable. You can describe, letter by letter any Python program you want. Letter by letter.
Not only its listing, but also its execution, step by step. So yes, English is computable.
I wonder whether we’re at cross purposes. I think you’re arguing that English is Turing-complete in the sense that you can describe in English any computational process you please; the question I posed was sort of dual to that, namely whether English is computable in the sense that there exists a computer program that perfectly distinguishes valid English sentences from everything else.
I think the boundaries of “valid English sentences” are fuzzy, which already makes that problematic. Otherwise, if we nail down the definition of “English” to something like “agreed by a majority of fluent English-speakers in April 2017 to be valid English” then the answer is probably yes because we can “just” simulate all those fluent English-speakers.
But, again, all that applies only to finite sentences. You want to allow infinitely long “sentences” too, and that opens up a whole lot of other cans of worms.
I don’t like infinity of any kind. I oppose it strongly, it’s a kind of mysticism by my view.
BUT, until it will still be officially permitted in mathematics, I will use it to discredit. To show how problematic it really is.
Ah, that explains a thing or two. You’re not trying (or at least not trying very hard) to make what you say make sense because you want it not to make sense, “to discredit”, and you don’t expect it to make sense because you’re using concepts you think don’t make sense themselves.
But the actual likely outcome is what’s happening here. No one is saying (and I bet no one is thinking) “this doesn’t entirely make sense—obviously the notion of infinity is problematic” but some people are thinking “huh, Thomas seems either confused or unreasonably unwilling to clarify”.
If you want to discredit something, the first step is to take it seriously.
The not so far away superintelligence will understand. ;-)
I came to the conclusion, that most people love the infinity so deeply and strongly for a reason. Otherwise their spiritual emptiness would be really unbearable. The infinity is a leftover after their abandoned religion, or a pillar of their actual religion.
So, no rational argument would probably do here.
That’s a nicely unfalsifiable bit of bulverism you’ve got there. I think I agree that “no rational argument would probably do”, but we may not mean the same thing by that.
[EDITED to add: I see no particular problem with the use of infinities in mathematics and never have; back when I was religious, I saw the mathematical notion of infinity as clashing a little with my notion of God—because in mathematics there is e.g. no all-surpassing maximal infinity—and I don’t recall ever, as theist or as atheist, “loving infinity deeply and strongly” or seeing mathematical notions of infinity as doing anything to create or fill “spiritual emptiness”. Of course introspection is unreliable, but it’s all I’ve got :-).]
I was always an non-spiritual atheist. (But I am a non-progressive, too,)
It may seems a bit naive, but when I have heard (as a child) about that paradox about omnipotent god who can’t create a rock so heavy that even he couldn’t lift … then I suddenly “knew” that quantities too big are (logically) problematic. Let alone infinite quantities.
Today, Yablo’s paradox is already good enough for me, to convince me that the infinity doesn’t work. How everybody doesn’t agree with me about this—baffles me.
Infinity is an abstraction that makes thinking about certain problems easier. It’s not a feature of reality (=territory), it’s a tool for thinking (=map). As with any tool, there are contexts where it is very helpful; there are contexts where it is inappropriate; and there are contexts where it can be misused.
Without the concept of infinity you’ll struggle with even basic geometry (consider a line) and calculus becomes an outright impossibility.
No matter, no matter. The fact that this concept of infinity sometimes makes our life easier, doesn’t make everything right about it. Maybe we should try harder. Going the right path isn’t always easy, it can be extremely hard. Perhaps unbelievably hard.
100 years ago, they thought that the self reflection is in the core of paradoxes, like Russell’s and related.
I thought long ago, that the infinity has its share here. With Yablo’s paradox, this is quite obvious. No self-reflection, but still a paradox. But if the Yablo’s list of statements is finite, than the last statement is true (vacuous truth), and—no problemo!
I can’t live with an infinite number of (even all finite) sentences. Because those statements may all be “every higher on this list statement is false”. But that would imply that the next statement is in fact true. Which means that this statement is false. But all saying the same, that would mean it is true. And so on in a circle.
I see a real paradox here, not a curiosum.
I may have misunderstood your argument Thomas. Are you saying that because it’s possible to construct a paradox ( in this case Yablo’s paradox ) using an infinitude, that the concept of infinity is itself paradoxical?
Couldn’t you make a similar argument about finite systems such as, say?:
A: B is false, B: A is false
Here are only two sentences. Is the number two therefore paradoxical? I apologize if it sounds like I’m trying to parody your argument—I really would like to learn that I’ve misunderstood it, and in what way.
I have to admit, that no. Perhaps it is something else wrong here. It might be. Not very likely, but still possible. We see, that finite lists don’t suffer because of Yablo’s paradox, infinite lists do. Still, it may be something else which really causes the A & NOT A situation..
You can. And you have a contradictory little system here. Which is therefore useless. So you take another one, like the rules for the game of chess. Hoping, that there is no paradox there. (But there is. You can’t believe it, but there is a paradox inside the chess rules!)
In practice, you can continue to play chess and use infinities. But that is at your own risk.
On which basis do you decide which path is right and which is not?
Are Zeno’s paradoxes also “real”?
No. Zeno paradoxes aren’t real. Why? You have to have an axiomatic system and inside this system you must be able to prove A & NOT A. Then and only then, there is a paradox.
Then EVERY statement is provable inside this axiomatic system and the system is useless.
Zeno had only “paradoxes”. Had he formulated one of his paradoxes inside geometry, that would be something! But he didn’t. All Zeno had was his intuition that “you can’t do infinite number of steps in a finite time”.
For the Russell’s paradox inside the Naive Set Theory, that is a different story. Using those axioms one can prove that his B is its own member. And one can also prove that it isn’t.
But those Cantor’s examples, like the Infinite Hotel—are NOT paradoxes. It is odd, and “paradoxical” if you wish, but that’s fine. Had Cantor proved, that this hotel can accommodate exactly 7 guests - and someone else (or Cantor) had proved that this hotel can accommodate exactly 12 guests—that would be a paradox indeed.
Assuming that both proofs were correct.
I know, you know that.
“you can’t do infinite number of steps in a finite time”
Well, can you? If some finite period must elapse when a finite distance is covered, an an infinite distance is greater than any finite distance, then the period of time elapsed in crossing an infinite segment must be greater than the period that elapses for crossing any finite segment, and thus also infinite.
I suppose you can also assume that you can cross a finite segment without a finite period of time elapsing—but then what’s to prevent any finite segment of arbitrary length being crossed instantaneously?
What seemed the infinite number of steps to Zeno (and pretty much to everybody else), may be only some finite number of Planck’s lengths to cross in some finite number of Planck’s time units.
(In the fifth century A.D., Indian mathematicians reconciled the doubts of Zeno, using infinite series and those solutions officially still hold. If you want to keep the infinitely divisible space and time, you may do it their way.)
So, Gödel?
He proved, that every system rich enough to contain “infinite arithmetics” is EITHER inconsistent (have paradoxes) EITHER have some non provable sentences.
Almost everybody thought—“Okay, okay, so we’ll always have nonprovables. It’s a shame, but what can we do?”
But this was not the only one explanation. The “Okay, okay so we can’t make the complete “infinite arithmetic” without a paradox. We must cease to even try that.”—flies at least as well.
I don’t know about that. They key word is “useful”. I’m not quite ready to discard and forget Peano arithmetic.
Yes, it is useful. Like a buggy program may be useful. But there comes the time of refactoring the whole thing.
Perhaps on an entirely new architecture.
What “A & ~A” did he prove?
He proved, that there is ALWAYS either at least one “A & ~A” (and therefore many) - either an unprovable theorem exists. Inside all those systems, which contain the “standard calculus”!
He didn’t prove an actual “A & ~A”, but that one always exists, if there are no unprovable theorems in those “standard calculus systems”.
That isn’t actually grammatical English, and unfortunately some plausible guesses at reconstructing it produce things that are completely false. So here’s what Goedel actually he did: he proved that for any powerful enough system either there is at least one (hence many) A & ~A, or there are A for which neither A nor ~A can be proved by the system.
That is almost correct. But “powerful enough” isn’t clear at all at your statement.
“Powerful enough” means those infinite sets with arithmetics.
It’s not “almost correct”, it’s actually correct. I wasn’t trying to make it complete :-). Yes, the “powerful enough” criterion is about being able to represent arithmetic. But if you want an actually-complete statement then “with arithmetics” and “contain the ‘standard calculus’” really aren’t any better than “powerful enough”. (I can never remember the exact requirements and am too lazy to look them up for this sort of discussion, and it’s not like the details matter very much here.)
Not only arithmetic, but an arithmetic with arbitrary large numbers is required for the Godel’s Incompleteness Theorem.
You need at least “all integers”, that is an infinite set.
Maybe some incompleteness can be proved for the finite sets as well. But it’s not known to be so. Nobody proved that yet.
Finite sets of numbers have obvious problems, well explored in computer science (if you integer has be be expressed in 4 bytes, you can express only a finite set of integers. Or real numbers, for that matter).
Trivially, if your finite set ends at n, what is the sum of (n-1) + (n-2)? A plausible answer is “you can’t do that”, but that’s also an answer to any paradox whatsoever.
How do you feel about imaginary numbers, by the way?
No, this is not true. The only answer we have to paradoxes is—change you axiom system!
There are no paradoxes there. At least no paradoxes which wouldn’t be present in the real numbers already.
SQRT(-1)=i is no paradox whatsoever. People might often say—“oh, well that’s paradoxical”.
No, it’s not. No A & ~ A here. It might be weird to somebody, that you can calculate square roots from negative numbers. I really don’t see why, but it might.
Weirdness and paradoxicality are two different things.
I don’t mind weirdness, I hate paradoxicality.
You can eliminate paradoxes by declaring operations which lead to them “illegal” (or their outcomes to be undefined).
Is i a number? If not, what is it? Does it have a sign?
Precisely! You narrow your axiomatic system, hoping that one of contradictors will fall out. They’ve eliminated self containing sets from the Naive Set Theory and Russell’s paradox vanished. Hopefully.
It is not “what is it”, it is “how does it behave”. Whatever behaves as a number, is a number.
If it behaves as it had a sign … And it does. So yes, it has a sign!
Which is what?
Everything which behaves like a sign.
“def” isn’t a word in the English language.
__init__isn’t either.But the English statement:
A Python program which begins with the letter “d”; followed by the letter “e”;....
is an English statement. Especially when it is a bit improved grammatically.
It is a sentence from a book written in English (maybe I should say ostensibly in English). Though to be fair the author isn’t English—he is Scottish :-)
It will not. It has no meaning in English.
Why not? It’s so defined, that it can explicitly describes any meaningful sentence in English. The question is only, can it describe all of them?
Of course it has. It means “Please transport me from the small building to the debris room.”
In the Silicon Dreams text adventure series (a sci-fi series) if you say “xyzzy” a robot will come up to you and assume that you are insane (since you are trying to cast a magical spell) and transport you to the appropriate place for insane people.
Good, “xyzzy” has meaning.
Then, like any other word, it can be invoked as:
...;now, the self description is paused, to discuss some words with “x”, “y” and “z” inside them … ;...
Jolly good. But I think your problem is not stated clearly enough to be soluble.
Gurkenglas solved it anyway.
Congratulations to Gurkenglas on guessing what you meant, then. Gg’s understanding differs from what I assumed, in so far as I was able to figure out your meaning, but the actual content of the puzzle was simple enough that I guess the obfuscation was most of the point.
I thought Gurkenglas’ solution was a lovely discrete math sledgehammer approach. There’s a lot of subtly different problems that Thomas could have meant and I think Gurkenglas’ approach would probably be enough to tackle most of them.
(Attempting to summarize his proof: Some English sentences, like the one this problem is asking you to dig around in, are countably infinite in length. If some English sentences are countably infinite in length, and any two of them have different infinite suffixes, then there’s no way the text of this sentence contains both of them.)
I think your summary is wrong, I’m afraid. The sentence could contain two different infinite suffixes—e.g., by interleaving them. (Well, maybe; it still isn’t clear to me what sort of descriptions Thomas is intending to allow.) The problem isn’t that having multiple infinite suffixes is a problem, it’s that (at least for certain rather non-standard notions of what a “sentence” is) there are uncountably many different sentences and if they all have to be described separately you’re dead.
If you allow one description to cover multiple sentences, though, you can cover all those uncountably many with something countably long. Suppose the words of the language are W1, W2, …, Wn and suppose a “sentence” is any string of finitely or countably many of them. (That’s not true for any actual natural language, of course, but this language does have uncountably many “sentences”.) Then you could say: “A sentence consists of the empty string, or: of one of W1,...,Wn followed either by the empty string or by: one of W1,...,Wn followed either by the empty string or by: …...”.
You could also, though this is a further step away from the sort of description I think Thomas wants to allow, do that in finite space. In fact, I already did, earlier in the paragraph above.
I think you’re right. I’m badly overlooking a subtlety because I’m narrowing “describe” down to “is a suffix of.” But you’re right that “describe” can be extended to include a lot of other relationships between parts of the big sentence and little sentences, and you’re also right that this argument doesn’t necessarily apply if you unconstrain “describe” that way. (I haven’t formalized exactly what you can constrain “describe” to mean—only that there are definitions that obviously make our sledgehammer argument break.)
I think “a sentence can be countably infinite” is implicit from the problem description because the problem implies that our “giant block of descriptions” sentence probably has countably infinite size. (it can’t exactly be uncountably infinite)
One of the problems was that Thomas spoke about a “natural language” that we all know what it looks like. And a natural language does not have infinite-length sentences.
Another is that Thomas’s question didn’t make it clear that each sentence covered had to be called out individually, as opposed to constructing some description that covers exactly the right sentences. Another is that even if we suppose our natural language augmented by allowing infinite sentences, it’s not clear that it should allow non-computable infinite sentences.
The whole discussion, plus the posted problem, plus the (re)defining the problem itself—is more interesting than the problem alone.
As I see it, these are my assertions:
an infinite sentence is possible whenever the infinity is permitted
with such an infinite sentence you can uniquely describe all the finite sentences
even if the infinite sentence is selfdescribing
with such an infinite sentence you can uniquely describe countably infinite number of infinite sentences, too
there are non-countably many such infinite sentences
some of them can be described by some finite sentence
every finite or infinite sentence can be uniquely described by some infinite sentence and also by non-countably many of them
there may be some finite self describing sentences in English
By selfdescribing I mean the Quine type of a sentence. A self reproducing sentence.
Funny, but the whole set of infinite sentences can be described by just one finite sentence.
Sure it does).
So what is this definition?
As far as I can see, your algorithm starts with a specific statement and then basically recurses forever creating the “mammoth statement”. But if you start with a different statement, you’ll get a different “mammoth statement”. And I still don’t see how one single “mammoth statement” will describe any meaningful sentence (and why the constraint on meaningful? meaningful to whom?)
Try again, still incomprehensible.
This (infinite) English statement describes itself to the letter.
It also describes some other English statements. The question is, is it possible that this statement describes all and every one of them?