![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 2010-10-11 11:34, Warp wrote:
> Tim Cook<z99### [at] gmail com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Tim Cook <z99### [at] gmail com> wrote:
> On 2010-10-11 11:34, Warp wrote:
> > Tim Cook<z99### [at] gmail com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |