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