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

Well, sure. Proving Fermat's Last Theorem is highly non-trivial. The 
result itself, though, is quite simple to explain.

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

Ah yes - it's a wetware issue...

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

Not really. It's just that usually the function's definition is a much 
more compact way to represent it. For example, AES takes a pair of 
256-bit inputs and produces a 256-bit output. It's totally finite. You 
*could* write down a table of all possible input/output combinations. 
All 2^512 of them.

Actually, screw that. Apparently there are about 10^80 atoms in the 
observable universe. And 2^512 is almost the square of that number. So 
no, technically you cannot "write down" the function table, because the 
universe isn't big enough...

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

More interestingly, if I add together infinity numbers of the form 
1/n^2, the answer appears to require an infinite amount of computation. 
And yet, Wolfram Alpha tells me, in finite time, that the answer is 
about 1.644. How impressive is that?

Mathematics is impressive partly because it sometimes lets you do 
seemingly impossible things like work out the answer to an infinite 
number of calculations.

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

Given that there are CAs which a Turing-complete, you have to wonder if 
you could wire together a handful of logic gates for each cell and make 
some kind of crazy supercomputer. Unfortunately, the problem then isn't 
going to be computing power, it'll be signal propagation speed...

>> Now I know why mathematics generally tries to avoid infinity whenever
>> possible...
>
> I don't think that's quite right. :-)

It's no secret that infinity has several extremely weird properties, and 
that you want to avoid using it unless you really can't avoid it.

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

Maybe it's like the Halting Problem though. You cannot determine whether 
every program does or does not halt. But you *can* determine whether 
*some* programs halt or not. Sometimes very easily, in fact.

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

It seems intuitively obvious that one thing with X possibilities and 
another thing with X+1 possibilities shouldn't be the same size. Then 
again Alpha0 + 1 = Aleph0, so what do I know?

Post a reply to this message