Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Does infinity exist?

plus.maths.org

Post reply on HN
Print view View original

71–80 of 127 posts

Re: Does infinity exist?

#71

Post by Dove »

Evbn wrote: post #64
Bakkot wrote: post #59

Earlier quoted context omitted.

> A strong AI can certainly do this. 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.

Re: Does infinity exist?

#72

Post by tikhonj »

DenisM wrote: post #47
tikhonj wrote: post #27

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…

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.

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.

Re: Does infinity exist?

#73

Post by Dove »

tikhonj wrote: post #70
Dove wrote: post #34

Earlier quoted context omitted.

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, enumerat…

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 so…

A chat program that hold up a conversation as intelligently as a human would be able to. And I suppose it needs access to the command line.

Re: Does infinity exist?

#74

Post by Evbn »

tikhonj wrote: post #27

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…

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)

Re: Does infinity exist?

#75

Post by tikhonj »

ced wrote: post #63
tikhonj wrote: post #27

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…

Nice post. 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…

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.

Re: Does infinity exist?

#76

Post by tikhonj »

Evbn wrote: post #74
tikhonj wrote: post #27

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…

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…

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.

Re: Does infinity exist?

#77

Post by Dove »

gjm11 wrote: post #68
Dove wrote: post #34

Earlier quoted context omitted.

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, enumerat…

What exactly do you mean by "strong AI"? 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.

Hence, it can't have source code.

Re: Does infinity exist?

#78

Post by Evbn »

Dove wrote: post #52
Dove wrote: post #34

Earlier quoted context omitted.

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, enumerat…

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.

My Mac can run Mac OS X in a VM and begin to execute the original Mac's inputs. It just won't finish.

Re: Does infinity exist?

#79

Post by Evbn »

DenisM wrote: post #47
tikhonj wrote: post #27

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…

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.

It was actually a muddled and incorrect proof. Joshzayin gives a correct proof below.

Re: Does infinity exist?

#80

Post by diminish »

jgrahamc wrote: post #9
ajanuary wrote: post #6

Earlier quoted context omitted.

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 occupie…

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 int…

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?

Post reply on HN