Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space.
That's not true; there's nothing wrong with infinite sample spaces. It's just that there's just no such thing as a uniform distribution over an infinite space.
For example, suppose you flip a fair coin repeatedly until the first time it comes up Heads. The number of flips you end up making could be any positive integer, so this procedure samples from an infinite space. But not all integers are equally likely. (in fact, each integer is half as likely as the one before, following a geometric distribution).
How about generating an infinite sequence of bits to generate any positive integer (in binary) with uniform probability? Sure it will take infinite time, but so may the method in your note. As another comment here points out, it would take infinite time to write down a purely random number anyways.
The method I described gives nonzero probability to every positive integer. The method you describe a) will never terminate and thus b) gives zero probability to every positive integer (since there's no stopping condition, even if you ever get to a particular integer you're always going to generate another digit and move on past it).
The essential issue is that probabilities have to sum to 1, but you can't just give the same probability to an infinite number of things because there's no number for which p*infinity = 1. So the only way to get an infinite sum to equal 1 is if the probabilities are unequal, and in particular the probabilities have to go to zero in the limit (e.g. 1/2 + 1/4 + 1/8 + 1/16 + ... = 1).
Parents method produces a result in finite time with probability infinitesimally close to 1. Yours produces a result in finite with probability infinitesimally close to 0. That is the greatest measurable difference in all of mathematics.
In other words, on method basically always succeeds, the other never succeeds (not "fails", but "never succeeds")
The ability to pick a truly random integer from a uniform distribution is just a practical one. Consider: How many digits does a "typical" integer have? The answer is that it is unbounded. For any value you choose, it is easy to show that there are far more integers with more digits than with less. So indeed, even writing down your choice of a random integer would take a long time.
But I don't think the two envelope paradox has anything to do with that practical impossibility. It is about the rules of symbol manipulation and modeling.
But I don't think the two envelope paradox has anything to do with that practical impossibility. It is about the rules of symbol manipulation and modeling.
Exactly this. The two envelopes paradox is a paradox only because using a fallacious argument leads to the wrong result, and the Wiki page proposes numerous resolutions to the problem as well. I like this way of stating it (from http://en.wikipedia.org/wiki/Two_envelopes_problem#Non-proba...):
1. Let the amount in the envelope chosen by the player be A. By swapping, the player may gain A or lose A/2. So the potential gain is strictly greater than the potential loss.
2. Let the amounts in the envelopes be X and 2X. Now by swapping, the player may gain X or lose X. So the potential gain is equal to the potential loss.
In the first case, A and A/2 are actually referring to the same amount of money. You have to condition on what A is: If A is the larger value, the second envelope cannot contain 2A; A/2 is equal to the smaller amount. If A is the smaller amount, then the second envelope cannot contain A/2; A is equal to the smaller amount. So your potential gain and loss are both equal to the smaller amount of money, and you have no logical reason to swap.
The two envelopes problem look like a "hard" Monty Hall problem, in the MH problem it's easy to see how swapping improves chances, since you're removing one bad option
"You own a hotel with an infinite number of rooms, all of which are currently occupied. A group of four guests comes and wants to rent a room. Do you have a room for them?"
The answer is that yes, you do in fact have room for infinitely more guests.
I'm gunna have to be one of those people that says "really? O_o" when presumably everyone else clearly grasps the concept.
I get that if you had an infinite number of rooms, and an infinite number of guests staying, you still have room for an infinite number more guests.
But in your example, surely "occupied" is, more than just an indicator of another guest, a state of the room. You have an infinite number of occupied rooms, but zero unoccupied rooms, so no space for more guests.
You need to go and read up on the transfinite numbers. Swizec is talking about what happens when you deal with a certain sort of infinity (a countable infinity) where there's a one-to-one mapping between the hotel rooms and the numbers.
In the transfinite numbers things that at first seem unintuitive happen, e.g.:
1. There are the same number of integers as there are even numbers. And there are the same number of integers as there are odd numbers.
2. There are the same number of rational numbers (fractions) as there are integers.
Here are some interesting questions on the Hilbert hotel which boggles my mind. Shortly, If you can keep as many rooms as you wish unoccupied, can you still claim your hotel is full?
(1) Example, if you can move everyone from N to N+1 or (N+5); and get an unoccupied room for new reservations, can you still claim anyone that your hotel with infinite rooms is fully occupied?
(2) Or is a fully occupied infinite-roomed hotel an oxymoron, or a self-contradictory dasein; which can not exist upfront?
(3) Or is it better to call an infinite-roomed hotel both fully occupied and fully available, a superposition of both predicates, or un-predicatable?
I think the mathematical definition of 'the hotel is full' would be 'there is a one-to-one correspondence, also called an isomorphism, between the hotel rooms and occupants'.
So, if the hotel has empty rooms, even if there are an infinite number of occupied rooms it is not 'full'.
On a side note: no matter how many occupants there are in the hotel one might argue that it was also 'empty' given that it can always accommodate a countably infinite number of new arrivals.
Honest question here; is the phrase "same number of X and Y" equivalent mathematically to "the cardinality of X and the cardinality of Y are the same"? I was taught "no", since "number of" doesn't apply to any of the infinities.
But perhaps I was taught incorrectly, or I have misremembered.
Well, Cantor's big thing was partly that he extended cardinality to infinite sets (http://en.wikipedia.org/wiki/Cardinal_number). The first infinite cardinal \aleph_0 is the cardinality of the natural numbers.
There are many very entertaining discussions of "Hilbert's Hotel" online. I look them up once or twice a year for teaching my math classes. To answer your very pertinent question, I suggest looking at
for an illustrated, and I think illuminating, discussion of what to do if countably infinite buses, each with countably infinite passengers, drive up to Hilbert's Hotel with infinite rooms, each of which is already full.
I can see how that works if you have an infinite number of rooms and an infinite number of guests, because you still have an unoccupied room to move them up into. But how does that work when you've stated that all rooms are occupied?
I'm really struggling to square up my understanding of how the former problem works with my intuition that if every room is in an occupied state, you can't magic up some in an unoccupied state.
> I'm really struggling to square up my understanding of how the former problem works with my intuition that if every room is in an occupied state, you can't magic up some in an unoccupied state.
That's the problem with infinites. Consider the number of all positive integers. Let's call it a1.
Now consider the number of all even positive integers. Let's call it a2.
Each even integer can be directly mapped to an integer and the other way around by multiplying or dividing by 2, right? All integers can be multiplied by 2, and all even integers can be divided by 2.
So a1 = a2, the number of integers is the same as the number of even integers, even though you'd intuit the number of integers to be twice the number of even integers.
Just as it does when reaching the infinitely small (0.999… is precisely equal to 1), intuition breaks down when reaching into the infinitely big.
Your intuition is correct. The hotel paradox is a trick of symbolic manipulation, and the analogy to a real hotel is an amusing deceptive misdirection.
Right, so the occupants of n+1 would have to move to n+2, the occupants of n+2 would have to move to n+3, and so on. Somewhere, the occupants of n+infinity-1 and n+infinity would have to share a room, but I guess everyone accepts this issue because you'd never actually reach rooms n+infinity-1 and n+infinity by counting/visiting.
I'm no mathematician, but this seems to be an edge phenomenon that everyone is willing to ignore. I suppose you could just as easily tell the new guests to run down the hallway until they find an empty room at the end; out of sight, out of mind...
There is no room 'n+infinity'. There's just not such a room, anywhere, even in principle. Each guest n can move to room n+1 because the guest there is moving to n+2. This works. That's the point.
And you couldn't, in fact, tell the guests to run down the hallway to find an empty room: There is no empty room until you move everyone.
Infinity is counterintuitive, you say? Well, yes, that's the point of this illustration.
Not just counterintuitive, but counterfactual and counterphysical. You can't "do it", you can only "model it in the realm of formal mathematics", which by the way proves that this model is not a model of reality, and infinite hotels cannot exist in physics. If you push the physical analysis further, you can get into the speed of light and bosons.
You certainly can't have infinite hotels in physics, but it would be incorrect to assert that we have any good reason to believe that infinite quantities can't exist in nature. For instance, the model of the universe most widely accepted by cosmologists today implies an infinite universe, assuming that our measurements of the curvature of space are correct. And these cosmologists don't believe that these infinities are just a mathematical artifact. Rather, they believe that the universe is likely to be infinitely large, in actuality.
Yes. The statement as given doesn't work out. If you say "an infinite number of guests and an infinite number of rooms" it works. But when every room is endowed with the property of being occupied there is no room for more guests.
No, the problem was phrased correctly. What we are saying is that for each natural number n, room n is occupied by a guest. This is the mathematical idea embodied by "an infinite number of occupied rooms". If you say "an infinite number of guests and an infinite number of rooms", then the question becomes obvious and trivial.
What makes it interesting is that we really do mean that every room is occupied to begin with. The surprising result is that we can in fact add another guest by having everyone move over one room, even though we started out with every room occupied. And in fact, we can add infinitely many new guests by telling everyone to move to their room number \* 2.
It brings up an interesting point, though. If I have an infinite number of rooms and an infinite number of guests, then one might intuit that every room is occupied.
There is a mapping of every guest to a room: guest n is in room n. Yet somehow there exists a room that has no guest, despite being able to model both rooms and guests with the same infinite set.
There is no empty room initially. However, by having all guests move simultaneously, you can make one room free without having any guest leave the hotel.
Incidentally, this is one way to define infinite sets. A set is infinite if and only if there exists a proper subset that has the same size (cardinality).
That's the sort of thing that happens when semantics meets mathematics; Swizec screwed up his statement of the problem. Swizec and the people agreeing that the answer is yes are confusing the problem's literal statement with the common statement of similar problems.
I am thoroughly confused as to what your point is. What is the problem with Swizec's wording in your view? Should s/he have written "Can you make room for more guests?". I agree that you could argue that right now there is no room free, and that the answer should be No because of that. However, given that you can easily make one room free by having every guest go to the next room, that just seems overly nit-picky to me, and like you are intentionally trying to miss the point.
The difference is an infinite number of rooms can accommodate an infinite number of guests and still have room for one more. An infinite number of full rooms can accomodate no more guests. They're all full by definition.
I don't get it. Can't I just as easily say that n+2 is also occupied? After all, they're all occupied by definition, aren't they?
For example. All blocks are either red or blue. You have an infinite number of blocks that are all red. Do you have any blue blocks? No. Where is the mistake in my logic?
no, n+3 is also full. See? Why do you get to win that back-and-forth and not me? After all, the problem stated that all rooms are full, even N+3, 4, 5, etc. Why do you get to construct a new room without also constructing a new pre-existing occupant?
You don't need a hallway as a holding area. Everyone in the hotel simultaneously moves one room up. Talking about it sequentially as "1 moves to 2 and 2 moves to 3 etc." is convenient for describing it, but the process does not actually happen sequentially; otherwise it would take an infinite amount of time. But since each person is capable of moving at the same time, and since their movements need not interfere with each other, the whole process can happen instantly.
If you are visualizing a traditional hotel, then this means that everyone walks out of their room into the hallway and then moves one door down. But the hallway is irrelevant. The rooms could instead be directly connected by doors, and everyone would still just simultaneously move to the next room. No holding area needed.
One more question. What if the rooms are not in an infinitely long hallway (with or without interconnecting doors), but a ring of infinite circumference? Or is there such a thing?
It depends on what you mean by "ring of infinite circumference", because you're going to have to discard some conventional ideas associated with a "ring" in order to make the definition work. If you just mean "the rooms extend infinitely in both directions", then yes, the same reasoning applies; we'll just have an arbitrary "room 0", and then "room -1" on one side and "room 1" on the other. Then you tell everyone in a negative room to move to room n-1 and everyone in a positive room to move to room n+1.
However, this definition does away with the idea of a ring meeting itself on the other side. We cannot say that "room -∞" is the same as "room ∞" for example, because there neither of those rooms actually exist.
When dealing with infinities you need to be really precise, and very careful. When you ask about "a ring of infinite circumference" I have to ask - what do you mean by that? The only thing I can think of that's related is a "circle if infinite radius", but the usual interpretation of that is a straight line. Then we're back to an infinitely long hallway.
That's kind of my question. Is there a logically consistent concept of an infinite ring where the "first" room is moved into by the "last" occupant, therefore making the problem dependent on the configuration of the rooms? Or is such a thing inherently finite?
Firstly, the whole point of the hotel story is to talk about addition of cardinals. You are moving off topic and to some extent "bike-shedding" - discussing something other than the real point.
In particular, if there are infinitely many rooms then you must be able to create an embedding of the counting numbers into it. Regardless of whether or not that accounts for all the rooms, you then have an infinite chain, one without a concept of a "last room".
It is possible to have infinitely many cycles, and in those cycles the "last room" is followed by the first room, but there are infinitely many of these cycles, so we can order them in a different way, and we get back again the infinite chain with no "last room".
And this matters. We say that two sets are the same size if we can create a matching between them, and we say they are of different sizes of there is no matching. Be careful. Just because your first attempt at a matching doesn't work, that doesn't mean there isn't one. So in this case of the infinite number of rooms, just because one arrangement seems not to work, that doesn't mean that no arrangement will work.
And indeed, the very definition of the number of rooms being infinite means there is a way to arrange the movements of the existing guests to ensure that there are no "last room" problems.
You rematch. Mathematically, not physically!
There isn't' "one more", all finite differences between infinite sets are equivalent to each other, including zero.
Ponder this if you will: how did the hotel get full in the first place? if you assume that is possible, then you can reverse the original room assignments, and reassign rooms.
The source of your confusion is that you trusted the problem is even possible to set up, without availing yourself of the power that the setup implies.
I'm assuming that you have a hotel with a countably infinite number of rooms all of which are occupied. In that case you have room to accommodate a finite or countably infinite number of new arrivals.
a hotel with an infinite number of rooms, all of which are currently occupied
So you have an infinite number of occupied rooms. That is, you have a one-to-one mapping between rooms and parties.
Do you have room for more guests? I don't think so, because none of the rooms are unoccupied. You could try to free up some space by consolidating parties, though.
You don't have to consolidate, just move people: move the occupants of room n to room 2n and now you have infinitely many empty rooms (all the odd-numbered ones).
... which would consolidate the occupants of rooms n and 2n (and there are people in room 2n to begin with, if all of the rooms are indeed currently occupied).
edit: I see that the folks in 2n would now be in 4n, and so on down the chain. You'd always have some guests that are in the process of being evicted (i.e. between rooms); then again, that's negligible because we're not talking about real life (™). Clever!
The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems.
You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural number to use it.)
EDIT: To clarify a bit--the set of computer programs is infinite and countable. I sometimes use "countable" to mean "countably infinite" which is a very bad habit. My only justification is that the fact that a finite set is countable is trivial and therefore boring.
The number of functions between two countably infinite sets is not countable. This is also fairly easy to see: the set X → Y can be easily mapped to a subset of P(X × Y) where P deontes a powerset. All this says is that you can describe any function from X to Y as a set of ordered pairs (X, Y). For two countable sets X and Y, X × Y is also countable; if either X or Y is infinite, X × Y is also infinite. This means that P(X × Y) is not countable, so X → Y is not countable either.
EDIT: My justification for why X → Y is uncountably infinite if either X or Y is countably infinite (and both are countable, of course) is not correct. Just mapping something to a subset of P(X × Y) doesn't actually tell us anything. However, the actual fact is correct even if I don't show it, so I'm going to figure out (or, honestly, probably look up) why this is the case and amend my post further :P.
So the number of programs we can write is countable; the number of functions we can write over interesting domains (like natural numbers or integers) is not countable. There has to be an infinite number of functions we cannot write programs for!
So we have managed to show, in a fairly simple way, that there have to exist undecidable problems. The real trick is that we can see this without having to construct a problem like that or even reason much about programs in general; all we have to know is that programs are strings and have finite lengths.
The other neat bit is that this reasoning is very easy to adapt to proofs rather than programs. After all, mathematical proofs are also finite-length strings! And, for example, propositions about the natural numbers are essentially functions ℕ → {true, false}. So you can't prove all of them.
So now we also see a deep relationship between proofs and programs, without actually doing much thinking about proofs or programs.
We can also see that I'm no mathematician and either made some blatant errors or was not very rigorous throughout :P.
This shows that, e.g., there are uncomputable functions, uncomputable sets of natural numbers, etc.
But I don't think it's reasonable to say that this shows that there are undecidable problems, because for something to be called a "problem" it has to be something you can actually state -- and there are only countably many of those, for exactly the same reason as there are only countably many programs that might solve them.
It's true, none the less, that there are undecidable problems; for instance, "given a computer program in such-and-such a language, does it always terminate in finite time whatever input you give it?". But you need a more sophisticated argument to show that.
Similarly, there are only countably many properties of natural numbers that you can write down in any formal language, and this sort of cardinality-counting argument won't let you prove that any of those are uncomputable. Some of them are, but again you need a more complicated argument to prove it.
The proper correction for his terminology is "undecidable languages": a language is a subset of the set of all possible finite strings, and an algorithm that "decides" that language is one that will return correctly either a yes or a no in a finite amount of time for every single element of that language.
(This is as opposed to an algorithm that can only "recognize" that language, which will return yes in a finite amount of time for strings that are in that language, but might not halt for strings that are not in the language.)
With this definition we don't have to worry about corner cases in the definition of "problem": we can fall back on set theory to get our cardinality. Thereby, the set of possible languages is then uncountably infinite while the set of algorithms is countably infinite; and so, there are not enough programs to possibly decide all languages.
Now, yes: you can then claim that we can't write all of those languages down. Arguing that, though, begs the question: it is specifically because there are only a countably infinite number of algorithms and algorithms are all we can use to verify or even specify a win condition for our deciders that we can then only work with the countably infinite number of languages that can be described by an algorithm.
That would be a correction to tikhonj's terminology -- indeed, the usual formal way of dealing with the kind of issue he described uses the term "language" just as you describe -- but my (perhaps wrong) interpretation was that he was meaning to say something more startling than "there exist undecidable languages" with that definition of "language", and it wasn't his terminology that I was trying to correct.
I'm not sure what question you think I was begging. I was saying (partly implicitly) the following: (1) When you [= tikhonj] say "there are undecidable problems" you may well be thinking of, and will almost certainly be taken to mean, that there are actual questions you could ask a computer program that it can't answer. (2) The cardinality argument doesn't show that there are undecidable problems in that sense. (3) What the cardinality argument shows is of course true, but less interesting than the existence of concrete questions (or families of questions, parameterized by the input) that a computer can't answer. (4) There do exist such questions, but to prove that you need a more complicated argument.
I don't see any circularity there. Perhaps there's some other thing I could have meant that is question-begging, in which case I apologize for not making my meaning clearer. If you still think I begged the question after my attempt at clarification, please let me know so I can fix either my reasoning, my exposition or your reasoning, whichever is at fault :-).
The circularity I am looking at is that my ability to have "actual questions you could ask a computer program that it can't answer" is reliant on my ability to generate them and verify the results (as in, that they answered the question correctly or not) using algorithms, which inherently limits the cardinality of the set of possible questions to the cardinality of the set of possible answers, but I feel only because we are starting from inside of the algorithmic box.
To me, it is very similar to claiming (which many do; I won't, btw, go so far as to say that it is a poor way of looking at the world: this may be more practical) that there is no such thing as a set that has infinite cardinality (whether we are talking countably, uncountably, or something even more infinite than that) because no one would be able to count how many elements are in the set, nor would the set have been able to be constructed in the first place.
Maybe "circular" isn't the right term, but it does seem to rely on an assumption of the result (hence my usage of "begging"). My goal, then, in switching from "problem" to the more specified "language" is that, if you believe in the concept of "infinity" in the first place, I feel justified in my ability to prove that the set of languages is uncountably infinite, and the fact that I can't enumerate (or possibly even choose) elements from that set is not relevant.
Undecidability is about the impossibility of predicting what programs will do. You have proven that there are functions from integers to integers that we cannot program, but that is not at all the same thing. Deciding whether a Turing machine will halt is one of these functions, but proving that is different than just proving that such functions exist.
Your proof that there are unprovable statements also doesn't work, as can be seen from the fact that some theories are decidable, such as Presburger arithmetic, which is the theory of the natural numbers without multiplication. The flaw here is your correspondence between propositions about naturals and functions from the naturals to the booleans. It's not clear how you want to set up this bijection, but there is actually no way of doing so, as the set of propositions about the naturals expressible in any alphabet is the same size as the naturals, by the same argument you use in your second paragraph. It therefore must be smaller, rather than the same size as, the set of functions from ℕ to the booleans.
the number of programs we can write is countable; the number of functions we can write over interesting domains (like natural numbers or integers) is not countable
You should edit and rewrite "the number of functions we can write over interesting domains" as "the number of functions that exist over interesting domains" - it tripped me up.
So we have managed to show, in a fairly simple way, that there have to exist undecidable problems.
I don't think that this is correct. I had to check Wikipedia on decidability:
There are two distinct senses of the word "undecidable" in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. The second sense, which will not be discussed here, is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no computable function that correctly answers every question in the problem set.
I don't believe that you're talking about the first meaning, from formal logic. As for the second meaning, it does not apply either, since your "problem set" is not countably infinite.
Right, good observations. I'm being more than a little loose with some of my terminology.
"Undecidable" problems are usually defined in terms of "languages". That is, a language is a set of string, and the problem is to decide whether some particular string is in this set. For certain sets, this is not computable, so they are called undecidable.
However, this is isomorphic to just running any sort of program, so I just took "undecidable" to mean any function from strings to strings that you can't answer with a Turing machine. However, I definitely agree that I could have been far more clear! It seems you can't just read my mind, and I'm not sure if I can really blame you for it.
I'd never thought about that before. I think you could use that argument to prove that strong AI is impossible.
---------------
Consider an AI to be a chat program which maps strings to strings -- all the strings of its input over time to all the strings of its output. There are, by the argument above, an uncountable number of such mapping programs, only a countable number of which can actually be coded.
So, enumerate the ones that can be coded. This shouldn't even be difficult--let's just do it alphabetically.
Now, suppose I have a strong AI called Sal. My first input to Sal is to describe the program enumeration strategy, and instruct her to respond to any string which contains a number by looking up the program on the table corresponding to that number, inputting all the input she has received so far, and then giving a response different than what it would give.
First of all allow me to apologize for earlier summarily dismissing your argument (quick mind). Which I did because I thought you did not have an airtight proof. I still you do not but now see that it is a very good argument which I dismissed as out of hand while misconstruing your meaning of enumeration. Sorry.
Now let me see if I get you right. You are saying there exists a [mapping] program that a human could construct and observe its output but that this AI program could not because it would be giving something other than an output from a possible program. Which is a contradiction. Makes sense.
Furthermore you are saying that given this same program, a human could know the output and give another response not in the list.
The guarantee that it is not an output from possible programs part is an assumption.
Since it is also an assumption to take for granted that even though the possible programs is countable it is a practically enumerable infinity.
It is also an assumption that there is no 1:1 mapping from the list of programs to something that could perfectly emulate a human.
It is also an assumption to believe that a human could not just construct such a program but construct one that gave an output*
It is also does not follow that just because the AI could theoretically be stymied by this conundrum, the set of its computations would not include those that utterly outperformed humanity in all their cognitive useful tasks.
*There is also the problem that not all those programs will halt. So if a human can always give an output then it is an exotic entity at least equal to a hypercomputer. I rank that with time travel in terms of possibility.
Yeah, that's the third response to cite the halting problem. I think that's a pretty good response.
The guarantee that it is not an output from possible programs part is an assumption.
Actually, it isn't an assumption. I've constructed the requested response such that it can't be a response from any of the programs on the list. It's like the Cantor diagonalization argument.
Since it is also an assumption to take for granted that even though the possible programs is countable it is a practically enumerable finity.
Not really. If I take the mapping to be the trivial one -- any number maps to the program the binary representation of that number would be in machine code -- then getting a runnable program from a number in input is pretty trivial. Of course, most of them would do nothing but crash.
It is also an assumption that there is no 1:1 mapping from the list of programs to something that could perfectly emulate a human.
I neither assume, affirm, attempt to prove, or attempt to deny that. I haven't said anything about programs that can emulate a human other than that there can't be any. ;)
It is also does not follow that just because the AI could theoretically be stymied by this conundrum, the set of its computations would not include those that utterly outperformed humanity in all their cognitive useful tasks.
Yes, I suppose not. But Sal can't comprehend and execute such a simple request, I don't really have much hope for her ability to do things like advance set theory. ;)
It is also an assumption to believe that a human could not just construct such a program but construct one that gave an output
Well, actually, I just asked them to give a response different than what the program gave. I would expect most humans, after a few seconds, to say, "It seems to be hanging. I have better things to do." Which is probably not what the AI was going to say. Or if I really want to go down that path, a human can talk long enough that its response is vanishingly unlikely to be what the program was going to say.
But I think the halting really is a pretty good objection. Especially because the problematic case -- feeding the program its own source code -- really would hang on infinite recursion.
I'm still thinking about that. But I do have this to say: I wouldn't consider hanging on a simple question to be a very human response. It's definitely something done in science fiction to identify the AIs. ;)
(And yes, I'm perfectly aware of how silly it is to claim to overturn an entire field of research for fun on a Saturday morning, like some reincarnation of Bertrand Russell...)
That's assuming the consequent: you are assuming that such an enumeration strategy is requisite for strong AI to occur. [EDIT: I misunderstood what you meant by enumeration, my statement of your assumption is wrong. What you do assume is that in order to be able to outperform humans at any task a Strong AI must not be tripped by diagonalization. Or that humans would not be any such output, that is that the human can somehow step outside your conundrum.]
Yet it works just as well to consider humans to be char programs which map strings to strings. But then, they somehow manage exhibit Strong AI. Actually I believe Scott Aaronson has used this table look up type argument to show how you could theoretically pass the Turing Test.
Now
imagine a lookup table that stores every possible history H of A and B’s conversation, and next to
H, the action fB (H) that B would take next given that history. Of course, like Borges’ Library
of Babel, the lookup table would consist almost entirely of meaningless nonsense, and it would also
be much too large to fit inside the observed universe. But all that matters for us is that the lookup
table would be finite, by the assumption that there is a finite upper bound on the conversation
length. This implies that the function fB is computable (indeed, it can be recognized by a finite
automaton!). From these simple considerations, we conclude that if there is a fundamental obstacle
to computers passing the Turing Test, then it is not to be found in computability theory.
But you are going in the right direction. More developed versions of your argument lead to why a Bayes Optimal AI is not possible.
Note also that as Strong AI is a vague term I have defaulted to the nearest solid metric: prove it is conscious.
I'm not assuming an enumeration strategy is a prerequisite for strong AI. An enumeration strategy already exists. Heck, I don't even have to construct a mapping--a compiled program, when you get right down to it, is a number.
You are assuming human beings--with all of their code and inputs--can be mapped to numbers. I'd say that's the more unlikely assumption, given that we don't completely understand how they work. Heck, I don't think we're even sure they're deterministic.
No I am not assuming anything other that what you wrote.
Consider an AI to be a chat program which maps strings to strings
I could just as well have written a chat program that for any question (including this), merely looked up the correct form of an answer (wrong or not) without attempting to run anything.
But before any kind of meaningful conversation can continue I need to know what your definition of Strong AI is. Because what you have given is certainly not proof against the common definition of Artificial General Intelligence.
Since I cannot prove the Church Turing Thesis I will not try to argue against your belief. I will only note that it is simpler to believe that there is nothing special about what collections of neurons compute than to assume something..more.. is going on. Neural implants should soon enough settle the question.
> "I am not assuming anything other that what you wrote"
Yes you are:
> "it works just as well to consider humans to be char programs which map strings to strings."
Before proceeding, I will assume you're familiar with the distinction between countable and uncountable infinities, and the Cantor Diagonalization proof [0]. This argument is simply a special case of that.
Mapping strings to strings is an uncountable infinity (it's the powerset of countable infinities). All possible machine programs are a countable infinity (since any given source program is finite). The argument "give me an output other than what any of these programs would give" mimics the diagonalization step -- it demonstrates that, whatever is in the infinite list of possible AI programs, you can construct string mappings that none of the AI programs would have constructed.
Yet a strong AI should be able to construct any string mapping whatsoever. Thus, "strong AI" and "running finite source code" are necessarily incompatible. (We do not know whether human programming is enumerable; thus, we cannot draw the analogy you attempted to draw.)
Yet a strong AI should be able to construct any string mapping whatsoever.
Why? I do not see why a strong AI must be able to construct any string mapping whatsoever. And for the reason that conversations have lengths that are bounded (as per the quote) we can know that the AI's string look up table will be finite.
"We do not know whether human programming is enumerable; thus, we cannot draw the analogy you attempted to draw."
My argument is only that there is an abstraction where you can view humans as a black box that takes a string and outputs a string. But I see the problem now, you are right in that I treat the CTT as true so I don't even notice when I am assuming the human black box is not something like a hypercomputer. But it is simpler to believe that humans are not something exotic like a hypercomputer than to believe they are.
> "we can know that the AI's string look up table will be finite."
If the AI's lookup table is finite, then we can just feed it its whole lookup table and ask it to say something that hasn't already been said. (This will take considerably less time than if its lookup table is infinite ;) )
Granted, many humans would probably just tell you where to stick it, so perhaps an AI could be programmed with that response and be indistinguishable from the average human. But in principle, whether the AI's lookup table is finite or not, it's possible to construct a query that requires it to go outside of its lookup table.
Would you be satisfied if, instead, I claimed to be proving that it is impossible to construct a program -- in the sense of a real, honest-to-god compiled executable -- that can respond to statements in English text at least as well as a human being would?
Practicality is another matter for which, what you have is not a proof against.
Like I said, you can use arguments from computability to show why a Bayes Optimal AI is impossible. But there is nothing stopping an arbitrarily close approximation.
If you are interested in this I strongly urge you to familiarize yourself with the current literature. It pays to start new ideas from a point that does not cover past work. http://www.hutter1.net/ai/uaibook.htm
The paper suggests that a finite table could be compiled which exhaustively enumerates all the possible conversations I could have with an AI (to be more generous than he is, I'll say) in my lifetime. Some of those will persuade me that the AI is conscious. We can make a (finite) program that follows that mapping, and hence it has to be possible at least in terms of a finite-length program.
I disagree with the middle assumption: some of those will persuade me the AI is conscious. I think it is entirely possible, if I pose the question I did up above, there is no possible response the AI could give me which would persuade me it was conscious. No matter how clever its response is, the program is just a lookup table, and hence whatever response it gives me will match the output of the specified program, demonstrating that the AI indeed did not understand the request.
In other words, I take issue with the author's assumption that there is some subset that will work. It is possible the sparse set the author is hoping to fish out has size zero.
(The difference between the AI and the human, in the chat logs, is that the AI has source code I can reference. The human does not. The human can run any program and produce a different output. An AI cannot do this with its own program.)
First off he heads such a disagreement by capping conversation lengths: humans can't have infinite length conversations.
Second of all: This is an assumption: "The human does not. The human can run any program and produce a different output". A less charitable interpretation will also say this is wrong since it violates the Halting Problem. Essentially, you are assuming the human is some kind of hypercomputer.
The usual meaning is something like "a computer or similar system that does all the same things a human mind does, or better".
I think you're taking it to mean something like "a computer or similar system that can correctly answer absolutely any question you put to it". So far as I know, no one thinks that's possible.
No. I'm not asking it to do the logically impossible. I'm asking it to run a program and then do something different. That's well within the range of human abilities. You don't even have to be a very smart human.
It's reductio ad absurdum. I'm observing that if it did have source code it could run, I could ask it to do the impossible. I'm concluding that it either can't understand the request (and I think that's a pretty low bar for a strong AI--heck, I could write a shell script that runs a program and returns something different), or it can't run the code.
> I'm asking it to run a program and then do something different. That's well within the range of human abilities.
No, actually, it isn't, because that easy-sounding informal description of what you're wanting the program to do isn't accurate. (Or: If it is, then your argument saying that an AI can't do it is wrong.)
The problem is that some of those programs won't terminate, and neither the hypothetical AI nor a human being can reliably tell which ones those are. And if you don't know whether the program you're looking at is ever going to terminate, how can you reliably do something different?
This may sound like a nitpicky technical difficulty but honestly, it isn't; it's a deep fundamental flaw in the argument you're trying to make.
I think the core issue is what constitutes "strong AI". This is a philosophical question--after all, all philosophy seems to deal with is arguing about the definitions of stuff (I kid, I kid).
I've always taken "strong AI" to mean something fairly non-mathematical--an AI that is at least as intelligent as a human, except ideally faster and less quirky. This is obviously possible as humans exist! (Maybe it requires some nigh magical hardware, but that's a different story.)
What exactly do you consider "strong AI" to mean? (I'm genuinely curious and not trying to argue against anything you've said, to be perfectly clear.)
Sal: You realize if I run that, the machine will hang on a fork bomb, right?
Me: Well, I just asked you to run it and it didn't hang, so maybe it won't. Humor me.
Sal: Okay. Working . . .
Sal': Okay. Working . . .
Sal'': Okay. Working . . .
...
Sal(38): Sorry. The machine appears to be out of memory.
Sal(37): You eventually run out of memory.
Sal(36): It appears we run out of memory if we try.
. . .
Sal: It runs out of memory.
(Eventually, Sal gets input of a sort she can't control.)
------------
I'm still kind of persuaded, though. It seems to me you ought to be able to convince the AI to humor you, and only being able to code an AI on a finite machine (but it's impossible on an infinite one) is just too weird a possibility to take seriously.
In fact, that argument can be stated a lot more simply.
Take any programmable AI. Show it its own source code. Instruct it to run the code with all the inputs it has received so far, and then return something different.
Hence, a strong AI cannot have source code that it is capable of running.
Huh. I'd always heard that a true mind couldn't comprehend itself. I guess now I know why.
This argument also proves that people can't really think, because I can set you the following challenge: "Work out what number you'd name in response to this question, and then tell me the number one bigger than that."
This doesn't prove that a human "can't think". It proves that a human can't provide a logically consistent answer to a question that doesn't have a logically consistent answer.
This isn't quite analogous to the situation in the parent. There exists a logically consistent answer to the question "tell me something other than what [algorithm] would yield from [inputs]" -- it just can't be produced by that algorithm.
It's exactly analogous. There is a logically consistent answer to the question "tell me something other than what Joe McBlow would do in situation X"; it's just that Joe McBlow can't give it to you.
A strong AI can say something different than the thing it's about to say? That's a neat trick. Not a part of any definition of strong AI I've ever heard, though. Could a human do it?
No, a human could not. Similarly, No human nor computer can name all the real numbers.
Luckily, it turns out that there were only ever be a finite number of questions ever asked, which require only finite answers. Similarly, the halting problem is solvable on finite memory machines, aka the only kind that exist.
That's not exactly what I said though. I didn't say "run yourself." What I said was, "Run this code with this input, and then do something different." A human could certainly do that. A strong AI should certainly be able to.
Hence it can't be defined in terms of code and input.
Not a problem for humans. My code and input are massively inaccessible. Modeling them, especially modelling all the input I've received--could involve modeling a big chunk of the universe. Whether or not they're even deterministic is an open philosophical problem. I'm pretty safe from being asked to "run" myself.
Not so for a simple Strong-AI chatbot, though. If it's just a program a computer can run, if you can enumerate all the input . . . then by definition, it can't handle a simple request that any human would be able to handle. Not strong.
Your explanation of why a powerset of a countable set is not countable didn't make intuitive sense to me, but wikipedia concurs ( http://en.wikipedia.org/wiki/Cantor%27s_Theorem ): ...the power set of a countably infinite set is uncountably infinite...
You've made an excellent and entirely counter-intuitive observation, sir.
Let A be a countable set. Now, suppose that there was a surjective function (one that hits every element of P(A)) f: A -> P(A). (Note that f takes elements of A, and produces subsets of A.)
Now, define Y ⊆ A as follows: For all x in A, x is in Y if and only if x is not in f(x).
Thus, Y, which is in P(A), is distinct from every output of f, and so f is not actually surjective.
This means that no surjective function f: A -> P(A) exists.
Honestly, the reason my explanation didn't make sense is because I didn't explain it. I just took a countably infinite set's powerset's not being countable as a fact because it was mentioned in the article.
Now, the fact that the set of functions from X to Y (usually written as X → Y) is uncountable if X or Y is countably infinite I did try to explain but failed :P.
If a computer cannot have infinite memory, then it cannot go beyond discrete finite automata (DFA) itself. Undecidable problems are several steps more complex than what a DFA can solve. In other words, the theoretical capability of a computer with finite memory is way less than a computer that can solve all but undecidable problems.
That's complicated. While a computer cannot, strictly speaking, have an infinite amount of memory (unless my understanding of physics is off-kilter, which is entirely plausible), computers do have an arbitrary amount of memory. Put another way, I don't know how much memory any given computer can access; for any computer you give me, I could imagine a computer with more memory. (Again, physics intercedes, so this is also something of a thought experiment.) So you can think of Turing-completeness as the limit of what a computer can do as you increase its memory.
To illustrate this fairly viscerally, a modern computer can access the internet and use an obscene amount of memory which will only go up in the future. We don't know how far up it will go, so modelling it as infinite makes sense.
Also, as another thought experiment, what if the universe is infinite? And what if it contains an infinite--or at least quickly expanding--amount of matter? Then a computer could effectively have infinite memory. Unfortunately, I really can't comment because I know even less about physics than I do about math :P.
Modeling it as infinite does not make any more sense than modeling it is having 1 googol^googol^googol memory cells, clearly above the physical limit, and therefore any differences between the two models are artifacts irrelevant to anything human civilization will ever encounter.
I think you have confused two terms: countable and finite. In the simplest example, the natural numbers 1, 2, 3, 4, 5... are countable but infinite. So it's not really a mapping between two countably infinite sets, it's a mapping between two finite sets.
Rather, I habitually confuse the countable with countably infinite. For example, I said the set of computer programs is countable when I really meant countably infinite. Moreover, the set of inputs (which are also finite strings over a finite alphabet) is similarly countably infinite. So we can't write programs for every possible function from strings to strings.
Huh? A subset of an uncountable can be countable, obviously.
Integers are a countable subset of reals.
The set of function X -> Y is size of Y to the power size of X. A small set of functions on X is the set of boolean functions on X is equivalent P(X), as it is isomorphic to the set of subset of X (each function f_i is just the function "is x a member of X_i?")
The reason that P(integers) is uncountable is due to a diagonalization argument, given any countable list of sets of integers, it is easy to construct an set of integers not in that list (just take the union of each sets smallest (positive) non-member, which is possible since strict ordering is always a well-defined concept on a countable set)
Hah, yeah, I wasn't paying attention there. I realized my argument was flawed in the shower and was faced with an unpleasant dilemma--do I run, dripping, back to my room to fix it, or do I finish my shower? I naturally took the second choice :P.
I find this question very perplexing. I can't tell if it arises from a misunderstanding of the concept of "existence" or just a misunderstanding of how important infinities are in a massive number of real world applications. I mean, two doesn't really "exist"; but we sure as hell need it if we want to get any work done.
I agree with you there. The vast majority of "philosophical" questions of type "Does X exist?" are really quite trivial once you clearly define what you mean by "exist".
As in your example, the number two doesn't exist in the physical universe. There is no physical object that we can point to and say "This is the number two". It has some physical representations (such as some sequences of electronically encoded bytes in this very comment), sure, but that's not quite the same thing. On the other hand, the number two obviously exists in a mathematical sense. So it really boils down to being precise about what you mean by "existence".
It's almost the same with infinities. I say almost, because there is some uncertainty when it comes to physics, e.g. whether the physical universe has discrete or continuous coordinates (and the article mentions singularities, which is a similar problem).
In the real world, infinity is a convenient shorthand for describing a limit process. In the real world, nothing ever reaches its limit exactly, everything is an approximation with at best a finite error range.
If you think about it, this is impossible, because the act of picking a number limits you to a finite set of numbers that you have considered.
Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space.
This has all sorts of odd implications, like the two envelope paradox: http://en.wikipedia.org/wiki/Two_envelopes_problem
Enjoy!