Invisible wrote:
> and then constructing a 

... arbitrarily large number of ...

> function from it which is different by construction 

> Well, let's face it, who actually understands what the hell Godel's 
> incompleteness theorems actually say?

I do, sort of. I understand what it means. I don't think I could reconstruct 
the proof from memory.

>>> That doesn't quite sound right...
>>
>> To translate it out of Wolfram self-congratulation-speak, he's saying
>> that there are no three-state turing machines that are UTMs.
> 
> Oh, right. That's quite trivial...

Not *that* trivial. Proving that isn't particularly easy, I think. But once 
you prove it, yeah, it's pretty straightforward. That's the Wolfram 
self-congratulation-speak of which I spoke. :-)

>> This is nonsense. I have no idea what you're trying to say. Where did
>> "hand-written" come into it? You're attacking a straw man.
> 
> I'm thinking "you can't solve the Halting Problem for any possible 
> program, but you use solve it for *useful* programs?" But, evidently, no 
> you can't.

No, you can't. Plus, useful programs are often interactive, so there's 
really not even any way to analyze most of them properly.

>> Funny enough, infinities make things much more complicated. That's why
>> virtually every bit of math deals with infinities.
> 
> Really? I had no idea that was true.

Sure. Almost all functions of interest have domains of infinite size, for 
example. Otherwise, you'd just list out what the function returns for each 
possible input and there wouldn't be any interesting abstract questions left 
about it.

>>> So it seems that the fallacy of solving the Halting Problem is in
>>> Magic() being able to predict the outcome of an infinite number of
>>> cycles of work with some finite number of cycles of processing.
>>> Interesting...
>>
>> Yes, exactly.
> 
> When you state it like that, it becomes "well *duh*, of *course* you 
> can't do that!" 

Except it really isn't "well duh" either. Would you say you can compile a 
program in a finite number of steps that you can't run in a finite number of 
steps? Of course. How different is "compiling" from "figuring out what the 
program does"?

>> Especially on a TM. A TM that runs for 1000 cycles can't write to 1001
>> cells. Which is, incidentally, why you only get "unbounded" output from
>> a TM, not infinite output. If you give a TM an infinite tape,it will
>> never all get used up.
> 
> Never? Or only after infinite time? *Is* there an "*after* infinite time"?

No, there isn't an "after infinite time", so ... never.

How many steps does it take to write the whole tape? Infinity. How many 
cells can you write in one step?  One.  How many steps do you have to run a 
TM before it has written the entire tape, by adding one more cell each time? 
I.e., how many times do you have to add 1 to a number before it hits infinity?

In contrast, how long does it take an instance of Conway's Life to rewrite 
an infinite number of cells?

> Now I know why mathematics generally tries to avoid infinity whenever 
> possible...

I don't think that's quite right. :-)

> Yeah, I still don't quite understand Rice's theorem. It seems to say 
> that *everything* is impossible, despite the fact that we actually *do* 
> it almost every single day. So that can't quite be right...

No. It's saying "if some programs/functions satisfy condition X, and some 
don't, then you can't write a program/function to figure out which satisfy X 
and which don't, because any such X can be turned into an instance of the 
halting program. The only ones you can test are ones where either every 
program does X or no program does X."

> If that's actually how it works, then the fact that there are more 
> partial than total functions is so jaw-droppingly self-evident that it's 
> quite a small proof.

I'm glad you're so brilliant. :-)  I'm glad you can intuitively determine 
whether one infinity is bigger than another infinity that way.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

Invisible wrote:
> In fact I've seen how there are different ways of representing real 
> numbers (ratios, continued fractions, radicals, etc.), and for almost 
> every one, there are some real numbers that do not have a finite 
> representation.

For *every* one, there are some real numbers that do not have a finite 
representation. That's what makes them irrational.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> For *every* one, there are some real numbers that do not have a finite 
> representation. That's what makes them irrational.

  "Some" is quite an understatement.

  The set of real numbers with a finite representation is countable, while
the set of real numbers without a finite representation is uncountable,
making the latter set much "larger". (The quotation marks are there because
both sets are infinite, so telling that one set is "larger" than the other
is a complicated subject, but in set theory even infinite sets can be larger
than other infinite sets, and that's the case here.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> For *every* one, there are some real numbers that do not have a finite 
>> representation. That's what makes them irrational.
> 
>   "Some" is quite an understatement.
> 
>   The set of real numbers with a finite representation is countable,

That's a good point. I hadn't actually thought of it that way. :-)

It also is interesting to consider things like Chaitin's number or "the 
smallest uninteresting number" or other finite descriptions that name a 
number but you can't tell which number they name.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

On 2010-10-11 11:34, Warp wrote:
> Tim Cook<z99### [at] gmailcom>  wrote:
>> How does a person go about deciding the same problem?  Or is that
>> impossible, too?
>
>    There are some programs that if you can prove if they will halt or not,
> you will receive 1 million dollars.

"Entropy exists, therefore this program will halt due to heat death of 
universe, if not sooner."

$1 mil, please.

XD

-- 
Tim Cook
http://empyrean.freesitespace.net

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> It also is interesting to consider things like Chaitin's number or "the 
> smallest uninteresting number" or other finite descriptions that name a 
> number but you can't tell which number they name.

  Well, not all numerical concepts have an actual numerical value because
there simply isn't a number that represents the concept. For example,
"the smallest real number which is larger than zero" does not exist.

  Other numerical definitions are inconcrete. For example 'epsilon' is an
"arbitrarily small positive quantity".

-- 
                                                          - Warp

Post a reply to this message

Tim Cook <z99### [at] gmailcom> wrote:
> On 2010-10-11 11:34, Warp wrote:
> > Tim Cook<z99### [at] gmailcom>  wrote:
> >> How does a person go about deciding the same problem?  Or is that
> >> impossible, too?
> >
> >    There are some programs that if you can prove if they will halt or not,
> > you will receive 1 million dollars.

> "Entropy exists, therefore this program will halt due to heat death of 
> universe, if not sooner."

> $1 mil, please.

> XD

  The halting problem is a problem of mathematics, not physics.

-- 
                                                          - Warp

Post a reply to this message

On 10/7/2010 8:59 AM, Darren New wrote:
> Look back over the diagonalization argument. There's no mention in there
> of what gets computed for who or what. It (basically) shows there are
> more partial functions than there are complete functions, so no complete
> function will be able to list all the partial functions.

Either I'm misinterpreting something or you didn't quite mean to type it 
that way, because as you put it that seems to be wrong.  Given two sets 
X and Y, I should think that there would only be more partial function 
from X to Y than total function when both X and Y are finite.  In the 
context of computable function both X and Y are generally assumed to be 
the set of natural numbers, so this wouldn't be the case.  Even if we 
restricted X and Y to finite sets, it still doesn't seem right since the 
denationalization you're trying to make work would need there to be 
using the number of programs which compute functions, rather than the 
number of functions itself.

Assuming that you were talking about "more programs which compute 
partial functions than programs which compute total functions" it still 
seems wrong, since I think it's pretty easy to show that there's 
countable infinitely many of each.

Am I missing something here?  Sure Rice's theorem can be proven with 
denationalization, but I don't think it has anything to do with the 
cardinality of sets (unlike, say, Cantor's denationalization).

Post a reply to this message

On 10/11/2010 12:33 PM, Warp wrote:
>>>     There are some programs that if you can prove if they will halt or not,
>>> you will receive 1 million dollars.
>
>> "Entropy exists, therefore this program will halt due to heat death of
>> universe, if not sooner."
>
>> $1 mil, please.
>
>> XD
>
>    The halting problem is a problem of mathematics, not physics.

Maybe Tim's a strict finitist, in which case your objection would be 
rejected on philosophical grounds?  Too bad that this stance would also 
keep him from using a reduction to the halting problem as a valid way to 
rephrase a conjecture, so no $1M all the same.

Post a reply to this message

On 10/11/2010 9:55 AM, Darren New wrote:
>>> Funny enough, infinities make things much more complicated. That's why
>>> virtually every bit of math deals with infinities.
>>
>> Really? I had no idea that was true.
>
> Sure. Almost all functions of interest have domains of infinite size,
> for example. Otherwise, you'd just list out what the function returns
> for each possible input and there wouldn't be any interesting abstract
> questions left about it.

Two comments:

1) There'd still be interesting questions to ask about partial 
functions, since I'm pretty sure the restriction of Rice's theorem to 
functions between finite sets still works (when the range and domain 
both have at least two elements, obviously).  It only gets 
`uninteresting' when you restrict yourself to a finite set of 
*programs*, not functions.

2) I don't agree with your view on the use of infinity in mathematics. 
On the contrary, infinity (or rather unboundedness, which I assume is 
that you meant) is often used as a way to *simplify* things.  I think 
that "big O" notation is an excellent example of this, but there's 
plenty of others.  Rather than type a bunch about it here, I managed to 
find a nice blog post about it: 
http://www.johndcook.com/blog/2010/09/09/infinite-is-easier-than-big/


>>>> So it seems that the fallacy of solving the Halting Problem is in
>>>> Magic() being able to predict the outcome of an infinite number of
>>>> cycles of work with some finite number of cycles of processing.
>>>> Interesting...
>>>
>>> Yes, exactly.
>>
>> When you state it like that, it becomes "well *duh*, of *course* you
>> can't do that!"
>

Except when you can.

Post a reply to this message