Does infinity exist? • Hacker News Board

Re: Does infinity exist?

#101

Post by Dn_Ab » Sat, Sep 15, 2012, 6:10 PM UTC

lotharbot wrote: post #98

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…

> "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 infi…

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.

Re: Does infinity exist?

#102

Post by damoncali » Sat, Sep 15, 2012, 6:11 PM UTC

Evbn wrote: post #89

damoncali wrote: post #19

Earlier quoted context omitted.

But how do you get a situation where there is one more room than occupants, if both are infinite and matched up?

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

The mixing of the possible with the impossible is certainly jarring.

Re: Does infinity exist?

#103

Post by ColinWright » Sat, Sep 15, 2012, 6:15 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?

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.

So - what do you mean?

Re: Does infinity exist?

#104

Post by gjm11 » Sat, Sep 15, 2012, 6:24 PM UTC

Dove wrote: post #77

gjm11 wrote: post #68

Earlier quoted context omitted.

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

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

Re: Does infinity exist?

#105

Post by gjm11 » Sat, Sep 15, 2012, 6:26 PM UTC

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.

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

Re: Does infinity exist?

#106

Post by saurik » Sat, Sep 15, 2012, 6:40 PM UTC

gjm11 wrote: post #66

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…

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

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.

Re: Does infinity exist?

#107

Post by saurik » Sat, Sep 15, 2012, 6:42 PM UTC

ced wrote: post #93

tikhonj wrote: post #75

Earlier quoted context omitted.

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

(You can try my description, a sibling to your more-parent comment, to see if that helps.)

Re: Does infinity exist?

#108

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

Dn_Ab wrote: post #101

lotharbot wrote: post #98

Earlier quoted context omitted.

> "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 infi…

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…

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

Re: Does infinity exist?

#109

Post by Dn_Ab » Sat, Sep 15, 2012, 6:55 PM UTC

Dove wrote: post #100

Dn_Ab wrote: post #96

Earlier quoted context omitted.

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…

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.

Re: Does infinity exist?

#110

Post by damoncali » Sat, Sep 15, 2012, 7:02 PM UTC

ColinWright wrote: post #103

damoncali wrote: post #57

Earlier quoted context omitted.

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?

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. So - what do you mean?

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?