Does infinity exist? • Hacker News Board

Re: Does infinity exist?

#91

Post by michaelcampbell » Sat, Sep 15, 2012, 5:38 PM UTC

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…

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.

Re: Does infinity exist?

#92

Post by Dn_Ab » Sat, Sep 15, 2012, 5:39 PM UTC

Dove wrote: post #84

Dn_Ab wrote: post #82

Earlier quoted context omitted.

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…

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

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.

Re: Does infinity exist?

#93

Post by ced » Sat, Sep 15, 2012, 5:43 PM UTC

tikhonj wrote: post #75

ced wrote: post #63

Earlier quoted context omitted.

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

Yeah, these problems are hard (and fun!) to think about. But I still don't understand how you can go from:

There has to be an infinite number of functions we cannot write programs for!

which is, of course, true, to

So we have managed to show, in a fairly simple way, that there have to exist undecidable problems.

I don't think that you are using "undecidability" in its correct sense, or perhaps I'm missing something. What is your undecidable problem? You wrote

the problem is to decide whether some particular string is in this set

Which set are you talking about? The set of all programs? How does that tie in with your functions defined on integers?

Re: Does infinity exist?

#94

Post by Dove » Sat, Sep 15, 2012, 5:48 PM UTC

Dn_Ab wrote: post #92

Dove wrote: post #84

Earlier quoted context omitted.

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

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

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?

Re: Does infinity exist?

#95

Post by alok-g » Sat, Sep 15, 2012, 5:48 PM UTC

tikhonj wrote: post #62

alok-g wrote: post #46

Earlier quoted context omitted.

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

Arbitrary here subtly includes infinite, since if it does not, then my argument is valid.

Re: Does infinity exist?

#96

Post by Dn_Ab » Sat, Sep 15, 2012, 5:51 PM UTC

Dove wrote: post #94

Dn_Ab wrote: post #92

Earlier quoted context omitted.

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

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?

I have already quoted a strong argument against such an impossibility: http://www.scottaaronson.com/papers/philos.pdf

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

Re: Does infinity exist?

#97

Post by Dove » Sat, Sep 15, 2012, 5:51 PM UTC

Dove wrote: post #34

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…

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 see two ways out of the dilemma.

Option 1:

Sal: Sorry Dave, I can't do that.

(So we just can't code strong, obedient AIs.)

----------

Option 2:

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.

Re: Does infinity exist?

#98

Post by lotharbot » Sat, Sep 15, 2012, 6:02 PM UTC

Dn_Ab wrote: post #92

Dove wrote: post #84

Earlier quoted context omitted.

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

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

> "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.)

[0] http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

Re: Does infinity exist?

#99

Post by mistercow » Sat, Sep 15, 2012, 6:04 PM UTC

damoncali wrote: post #57

mistercow wrote: post #55

Earlier quoted context omitted.

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…

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.

Re: Does infinity exist?

#100

Post by Dove » Sat, Sep 15, 2012, 6:08 PM UTC

Dn_Ab wrote: post #96

Dove wrote: post #94

Earlier quoted context omitted.

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?

I have already quoted a strong argument against such an impossibility: http://www.scottaaronson.com/papers/philos.pdf 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 fam…

I disagree. Here is the resolution.

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.)