 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Ah yes, it is impossible to write a computer program that can analyse
any possible computer program and tell you whether it halts in a finite
number of steps.
After reading about Cantor's diagonal argument, the cardinality of the
continuum, Turing degrees, and other mind-blowing stuff, it seems that
the *reason* the Halting Problem is undecidable boils down to this:
If there was a Magic() subroutine that could take the object code to
your whole program and tell you whether it halts or not, then you could
write a BlackMagic() subroutine that calls Magic(BlackMagic()) and then
purposely does the opposite of whatever Magic() claims that it's going
to do. Hence, it is impossible for Magic() to yield the correct answer,
since BlackMagic() will do the opposite of whatever Magic() claims it
will do.
Interestingly, even if you build some kind of hyper-computer that can
solve the Halting Problem, then by the argument above you could define a
new Hyper-Halting Problem which the hyper-computer would be just as
powerless to solve.
Looking the other way, the argument above doesn't work if the program to
be analysed isn't allowed to call Magic(), or perhaps one of the
operations used within Magic(). Which seems to just restate the fact
that a system can only prove results about systems weaker than itself.
Oddly enough:
http://mathworld.wolfram.com/HaltingProblem.html
"The halting problem is solvable for machines with less than four states."
That doesn't quite sound right...
The Halting Problem cannot be solved. You cannot write a program which
can decide for *every possible program*. But can you write one for "the
kind of programs that human beings tend to write"?
Well, first of all, good luck finding a rigorous definition for "the
kind of programs that human beings tend to write". But, assuming you
find one, the argument above still seems to apply. In other words, if it
*is* somehow possible to write a program that can determine whether
hand-written programs halt, the solution program cannot be hand-written. (!)
Another puzzling thing: Deciding whether a program halts within, say,
1000 steps *is* trivially solvable. Just run the program for (up to)
1000 steps, and see if it halts.
It's quite obvious that that ought to work. However, it looks like the
argument above should still apply, making it impossible to solve this
problem.
So what happens if you implement Magic() this way? Does BlackMagic()
halt or not halt? It seems that BlackMagic() would immediately call
Magic(), which would immediately begin simulating BlackMagic(), which
would immediately call Magic(), which would start simulating
BlackMagic()... Eventually, at some point, the top-level Magic() would
give up on its simulation and report back to the top-level BlackMagic()
that BlackMagic() takes more than 1000 steps to execute. Whereupon...
...Magic() has already used up thousands of cycles, and therefore
BlackMagic() can't be contrary and halt in less than 1000 cycles to
invalidate the analysis. Ah, trixy!
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...
That suggests another interesting question: Can you write a program that
takes any possible terminating program, and yields the same result in
strictly fewer steps? (E.g., if program P yields a result in K steps,
program Q given program P as input yields the same result in only K-1
steps.)
Unlike the Halting Problem, nobody would seriously expect the answer to
be no. Which is interesting, because when you think about it, they're
very similar programs really.
If Magic(P) computes the same thing as P but takes exactly 1 fewer
steps, then Magic(Magic(P)) computes the same thing in 2 fewer steps.
And by induction, by applying Magic() enough times, any result can be
computed in zero steps, which is impossible. Hence, Magic() does not
exist (or at least, doesn't work properly).
Here we're talking about *computation* compression, which is not unlike
the *data* compression case. If a compression algorithm could always
compress data by at least 1 bit, you could compress anything into zero
bits. And, conversely, decompress zero bits into anything. The latter is
obviously impossible.
The way the theorem is usually phrased is that "K bits can represent 2^K
possibilities, but K-1 bits can only decompress into 2^(K-1)
possibilities, which is *half* as many". I suppose you could relate the
number of cycles that a program runs for to the number of possible
outputs it can generate and prove it that way...
I note with some interest that if it's impossible for a program to not
halt, then the Halting Problem becomes [trivially] solvable. That's
cute. But why is it true? Because BlackMagic() tries to not halt if
Magic() says it should halt. It non-termination is impossible, then
BlackMagic() cannot have its evil way.
In fact, it seems that Magic() can function correctly so long as you
can't implement BlackMagic(), or something equivalent to it. So if you
want to know how to make the Halting Problem tractable, maybe you just
need to look at what components are required to implement BlackMagic()
[assuming that Magic() already exists].
For example, it appears as if it ought to be possible to implement
Magic() as a partial function that is defined only for programs that do
not call Magic(), nor contain an instruction sequence isomorphic to it.
In reality, I guess that might be quite a big limitation. For example,
there is Rule 30. This cellular automaton can be computed by the logic
function Y' = X xor (Y or Z). So I imagine with just a few bitwise (or
even integer arithmetic) instructions, you could implement Rule 30. And
it's known to be Turing-complete. Oh dears...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> the *reason* the Halting Problem is undecidable boils down to this:
That's just one of the proofs. The diagonalization proof is another. There
are many programs (most?) that you can prove you can't analyze.
> Looking the other way, the argument above doesn't work if the program to
> be analysed isn't allowed to call Magic(), or perhaps one of the
> operations used within Magic(). Which seems to just restate the fact
> that a system can only prove results about systems weaker than itself.
Yes. There are a number of problems about sets of integers that you can
prove are true and can prove are unprovable in more powerful mathematical
systems. I.e., Godel's incompleteness doesn't apply only to Godel strings.
> 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.
> The Halting Problem cannot be solved.
It *can*, if your machine isn't sophisticated enough to represent the integers.
Can you solve the halting problem for all computer languages with no
indefinite loops? Of course - they all halt.
> can decide for *every possible program*. But can you write one for "the
> kind of programs that human beings tend to write"?
I don't know why you think a machine with less than four states represents
programs humans tend to write.
> Well, first of all, good luck finding a rigorous definition for "the
> kind of programs that human beings tend to write". But, assuming you
> find one, the argument above still seems to apply. In other words, if it
> *is* somehow possible to write a program that can determine whether
> hand-written programs halt, the solution program cannot be hand-written.
> (!)
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.
> Another puzzling thing: Deciding whether a program halts within, say,
> 1000 steps *is* trivially solvable. Just run the program for (up to)
> 1000 steps, and see if it halts.
Funny enough, infinities make things much more complicated. That's why
virtually every bit of math deals with infinities.
> It's quite obvious that that ought to work. However, it looks like the
> argument above should still apply, making it impossible to solve this
> problem.
What argument? The one about programs written by hand?
> So what happens if you implement Magic() this way?
What way? By asking how many steps? No, you have a completely different
function. Figuring out if something halts in 1000 steps is done completely
differently from figuring out if it halts ever, exactly because if the
answer is "no" then you can't simulate the thing you're analyzing long
enough to figure it out.
> 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.
> That suggests another interesting question: Can you write a program that
> takes any possible terminating program, and yields the same result in
> strictly fewer steps? (E.g., if program P yields a result in K steps,
> program Q given program P as input yields the same result in only K-1
> steps.)
No.
> Unlike the Halting Problem, nobody would seriously expect the answer to
> be no.
I suspect, given your later writing, you meant "yes" in that sentence.
> The way the theorem is usually phrased is that "K bits can represent 2^K
> possibilities, but K-1 bits can only decompress into 2^(K-1)
> possibilities, which is *half* as many". I suppose you could relate the
> number of cycles that a program runs for to the number of possible
> outputs it can generate and prove it that way...
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.
> I note with some interest that if it's impossible for a program to not
> halt, then the Halting Problem becomes [trivially] solvable. That's
> cute. But why is it true? Because BlackMagic() tries to not halt if
> Magic() says it should halt. It non-termination is impossible, then
> BlackMagic() cannot have its evil way.
Sounds like you're on your way to Rice's Theorem.
http://en.wikipedia.org/wiki/Rice%27s_theorem
> In fact, it seems that Magic() can function correctly so long as you
> can't implement BlackMagic(), or something equivalent to it. So if you
> want to know how to make the Halting Problem tractable, maybe you just
> need to look at what components are required to implement BlackMagic()
> [assuming that Magic() already exists].
The halting problem only makes sense in the context of partial functions.
> For example, it appears as if it ought to be possible to implement
> Magic() as a partial function that is defined only for programs that do
> not call Magic(), nor contain an instruction sequence isomorphic to it.
Not really.
> In reality, I guess that might be quite a big limitation. For example,
> there is Rule 30. This cellular automaton can be computed by the logic
> function Y' = X xor (Y or Z). So I imagine with just a few bitwise (or
> even integer arithmetic) instructions, you could implement Rule 30. And
> it's known to be Turing-complete. Oh dears...
Right. Exactly. There are an infinite number of programs isomorphic to
BlackMagic, and you can't tell which they are. Plus, even if you disallow
BlackMagic, you still haven't proven the existence of Magic. You've just
ruined one proof of it.
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.
--
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 <voi### [at] dev null> wrote:
> If there was a Magic() subroutine that could take the object code to
> your whole program and tell you whether it halts or not, then you could
> write a BlackMagic() subroutine that calls Magic(BlackMagic()) and then
> purposely does the opposite of whatever Magic() claims that it's going
> to do. Hence, it is impossible for Magic() to yield the correct answer,
> since BlackMagic() will do the opposite of whatever Magic() claims it
> will do.
That's just the simplest proof. It doesn't mean it's the only one, or
that the only way of making an undecidable algorithm is by making it call
the halting problem solver itself.
While this is not a proof of anything, it's however, a marvelously simple
example of why solving the halting problem is extremely difficult:
"A program that goes through all even numbers and checks if one of them
is a counter-example to the Goldbach's conjecture. The program terminates
when it finds the first such number."
An algorithm which solves the halting problem would prove (or disprove)
the Goldbach's conjecture with its answer (if the answer is "it never
halts", then it proves the conjecture, while the answer "it halts"
disproves it, and this disproval would be valid even if it couldn't give
the counter-example).
How could an algorithm resolve whether that program will ever halt or not?
Top mathematicians have struggled with that problem for over 250 years, to
no avail. A program which solves the halting problem for any given program
would make proving basically *all* mathematical problems trivial.
While, as said, this is not a proof that it's not possible, it gives a good
idea why it would be a tremendously difficult problem to solve.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> An algorithm which solves the halting problem would prove (or disprove)
> the Goldbach's conjecture with its answer
FWIW, Rice's Theorem basically say *any* property that some but not all
functions have can be turned into the halting problem. So if there's
anything non-trivial you want to find out about what a function computes,
it's just as impossible to compute as the halting problem is.
--
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:
> Warp wrote:
> > An algorithm which solves the halting problem would prove (or disprove)
> > the Goldbach's conjecture with its answer
> FWIW, Rice's Theorem basically say *any* property that some but not all
> functions have can be turned into the halting problem. So if there's
> anything non-trivial you want to find out about what a function computes,
> it's just as impossible to compute as the halting problem is.
One interesting thing about the example I mentioned is that the program
in question is quite short. I'm sure you could write the program in 2 or 3
lines of Haskell (of course it has to assume integers of unlimited size and
an unlimited amount of RAM). Yet proving whether this extremely short program
will ever terminate has puzzled top mathematicians for over 250 years.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 2010-10-07 09:43, Invisible wrote:
> Ah yes, it is impossible to write a computer program that can analyse
> any possible computer program and tell you whether it halts in a finite
> number of steps.
How does a person go about deciding the same problem? Or is that
impossible, too?
--
Tim Cook
http://empyrean.freesitespace.net
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Cook wrote:
> On 2010-10-07 09:43, Invisible wrote:
>> Ah yes, it is impossible to write a computer program that can analyse
>> any possible computer program and tell you whether it halts in a finite
>> number of steps.
>
> How does a person go about deciding the same problem? Or is that
> impossible, too?
That's impossible too.
Is this true or false: "I am lying."
That's just one of the sorts of problems.
Note that there are many individual problems where you *can* figure this
out. It's just that there's no way to figure it out for *all* problems, and
no way of categorizing in advance which ones you can figure it out for and
which you can't.
--
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 10/10/2010 08:57 AM, Warp wrote:
> While this is not a proof of anything, it's however, a marvelously simple
> example of why solving the halting problem is extremely difficult:
>
> "A program that goes through all even numbers and checks if one of them
> is a counter-example to the Goldbach's conjecture. The program terminates
> when it finds the first such number."
>
> An algorithm which solves the halting problem would prove (or disprove)
> the Goldbach's conjecture with its answer (if the answer is "it never
> halts", then it proves the conjecture, while the answer "it halts"
> disproves it, and this disproval would be valid even if it couldn't give
> the counter-example).
>
> How could an algorithm resolve whether that program will ever halt or not?
> Top mathematicians have struggled with that problem for over 250 years, to
> no avail. A program which solves the halting problem for any given program
> would make proving basically *all* mathematical problems trivial.
>
> While, as said, this is not a proof that it's not possible, it gives a good
> idea why it would be a tremendously difficult problem to solve.
My favourite one is determining whether a point belongs to the
Mandelbrot set. The program to do this is about 3 lines long. Depending
on which point you choose to investigate, the program will either loop
forever (indicating that the point belongs to the M set) or halt after
finite iterations (indicating that the point belongs to the complement
of M).
The trouble is, the most celebrated single property of the M set is that
it's absurdly complicated.
When I was a teenager, I used to think that maybe instead of blindly
iterating the equations, you could use the geometric properties of the
set to figure out the answer faster. But now I realise that since the
geometric forms repeat to infinity as well, there are still points which
would be just as slow to categorise that way.
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. It seems reasonable that no matter what algorithm you
use for determining membership of M, there will still be cases requiring
infinity iterations.
No matter which way round you look at it, it's just not solvable in
finite time, *every* time.
And this is just one of the possible computer programs you could write.
We haven't even considered any of the more complicated generalised sets
one might contemplate. An algorithm that knows the special properties of
every single set mathematically definable so that they can all be
resolved in finite time? I double it...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 07/10/2010 04:59 PM, Darren New wrote:
> Invisible wrote:
>> the *reason* the Halting Problem is undecidable boils down to this:
>
> That's just one of the proofs. The diagonalization proof is another.
The proof involving BlackMagic() is only a very slight variation on
diagonalisation. (That argument seems to work by constructing a binary
function over the program and its input, and then constructing a
function from it which is different by construction from any possible
computable function, demonstrating that the halting function isn't
computable. Or something like that.)
>> Looking the other way, the argument above doesn't work if the program
>> to be analysed isn't allowed to call Magic(), or perhaps one of the
>> operations used within Magic(). Which seems to just restate the fact
>> that a system can only prove results about systems weaker than itself.
>
> Yes. There are a number of problems about sets of integers that you can
> prove are true and can prove are unprovable in more powerful
> mathematical systems. I.e., Godel's incompleteness doesn't apply only to
> Godel strings.
Well, let's face it, who actually understands what the hell Godel's
incompleteness theorems actually say?
>> 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...
>> The Halting Problem cannot be solved.
>
> It *can*, if your machine isn't sophisticated enough to represent the
> integers.
>
> Can you solve the halting problem for all computer languages with no
> indefinite loops? Of course - they all halt.
Which is the conclusion I also came to a few lines down. ;-)
>> can decide for *every possible program*. But can you write one for
>> "the kind of programs that human beings tend to write"?
>
> I don't know why you think a machine with less than four states
> represents programs humans tend to write.
No, this is a new line of thinking, not an extension of the previous one.
> 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.
> 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.
>> It's quite obvious that that ought to work. However, it looks like the
>> argument above should still apply, making it impossible to solve this
>> problem.
>
> What argument? The one about programs written by hand?
No, the one about using BlackMagic() to break Magic().
>> 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!" And yet, stated the original way, it looks like figuring
out whether a program halts ought to be "really easy" for some reason...
>> That suggests another interesting question: Can you write a program
>> that takes any possible terminating program, and yields the same
>> result in strictly fewer steps?
>
> No.
And nobody is surprised about this. (As I intended to type...)
>> The way the theorem is usually phrased is that "K bits can represent
>> 2^K possibilities, but K-1 bits can only decompress into 2^(K-1)
>> possibilities, which is *half* as many". I suppose you could relate
>> the number of cycles that a program runs for to the number of possible
>> outputs it can generate and prove it that way...
>
> 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"?
Now I know why mathematics generally tries to avoid infinity whenever
possible...
>> I note with some interest that if it's impossible for a program to not
>> halt, then the Halting Problem becomes [trivially] solvable. That's
>> cute. But why is it true? Because BlackMagic() tries to not halt if
>> Magic() says it should halt. If non-termination is impossible, then
>> BlackMagic() cannot have its evil way.
>
> Sounds like you're on your way to Rice's Theorem.
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...
> 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.
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.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> `uninteresting' when you restrict yourself to a finite set of
> *programs*, not functions.
Well, Rice's theorem, yes. I was speaking of mathematics in general.
> 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.
Well, the existence of infinities in your inputs complicate things more than
a system where everything is finite. A turing machine with a fixed-length
tape is far less interesting to prove things about than otherwise.
Stuff like big-O notation only uses infinities because you're again assuming
your functions have infinities in them. Every program on a finite machine
finishes in O(1) time.
But yes, certainly I didn't mean to imply using infinities is always more
complex than trying to avoid them in a problem where it's appropriate.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> 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.
That's a point. I probably don't understand it as well as I think I do. :-)
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> 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.
Sure. But Chaitin's number *does* have a value. It's just defined in a way
that you can't compute it. (Basically, "the probability that an arbitrarily
selected program will halt", along with of course all the definitions and
such to make that meaningful mathematically.)
And "the smallest uninteresting number" doesn't exist because the definition
is self-contradictory.
--
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 11/10/2010 05:56 PM, Darren New wrote:
> 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.
No, not having a finite ratio representation makes a number
"irrational". Not having a finite polynomial representation makes it
"transcendental". And so on and so forth.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 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".
On the other hand, the distinction is typically irrelevant. Usually you
don't actually "need" the precise value of (say) Sqrt(2); some rational
approximation is sufficient.
Perhaps for similar reasons, you don't often come across real numbers
that aren't compactly representable...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 11/10/2010 05:34 PM, Warp wrote:
> There are some programs that if you can prove if they will halt or not,
> you will receive 1 million dollars.
http://www.zetagrid.net/
These guys spent years trying to prove the Riemann Hypothesis by seeing
if a computer program ever halts...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>>> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>
> Well, the existence of infinities in your inputs complicate things more
> than a system where everything is finite. A turing machine with a
> fixed-length tape is far less interesting to prove things about than
> otherwise.
This is generally true if you have actual infinities as inputs, but for
the case when you merely have arbitrarily large (but always finite)
inputs I'm actually having trouble thinking of a case where this is true
that doesn't involve only "small" finite values (or in which you allow
some unbounded quantities but not others, like in your comment on finite
programs being O(1)). Perhaps you had an example in mind?
I'm more used to seeing "arbitrarily large" or "arbitrarily small"
values used to simplify things.
> Stuff like big-O notation only uses infinities because you're again
> assuming your functions have infinities in them. Every program on a
> finite machine finishes in O(1) time.
>
My example with big-O notation was actually slightly different than
that. If we really restrict ourselves to only bounded quantities, then
it's impossible to actually define big-O notation since it's defined for
"sufficiently large inputs". Thus saying that every program on a finite
machine finishes in O(1) times is sort of disallowing infinity in one
area while letting it slip by in another.
My point with big-O notation was instead that the allowance of
arbitrarily large inputs in the definition is actually massively
simplifies the problem. Without it we'd probably be restricted to an
analysis where constant multiples in the running times really do matter,
making it much harder to analyze the running times of programs in a
general way.
Thus I think it's misleading to say that "big-O notation only uses
infinities because you're again assuming your functions have infinities
in them". Rather big-O notation uses infinities because it greatly
simplifies the analysis of programs (and it practice it turns out that
the analysis for the case with arbitrarily large inputs carries over
pretty well to the real-world case of large but bounded inputs).
I'm not entirely sure that we actually have different viewpoints on
this, and it's possible that I'm just misunderstanding your argument.
I'm mostly basing my assumptions about your position on your comment:
> Funny enough, infinities make things much more complicated. That's why
> virtually every bit of math deals with infinities.
Which seems to run counter to my experience, where I'm used to seeing
unbounded values allowed as a simplifying assumption, and see them as
common because it's such a powerful tool for allowing general statements
about whatever branch of math you're considering.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> inputs I'm actually having trouble thinking of a case where this is true
I don't know what "this" you're talking about. Your comments don't make
sense in the context of the bit you quoted.
> My example with big-O notation was actually slightly different than
> that.
Right.
> Thus saying that every program on a finite
> machine finishes in O(1) times is sort of disallowing infinity in one
> area while letting it slip by in another.
Basically, yes.
> My point with big-O notation was instead that the allowance of
> arbitrarily large inputs in the definition is actually massively
> simplifies the problem.
I didn't mean to say it didn't. I thought I had only said it was more
interesting with infinities.
> I'm not entirely sure that we actually have different viewpoints on
> this, and it's possible that I'm just misunderstanding your argument.
> I'm mostly basing my assumptions about your position on your comment:
>
>> Funny enough, infinities make things much more complicated. That's why
>> virtually every bit of math deals with infinities.
>
> Which seems to run counter to my experience,
In many cases where everything is finite, the math becomes trivial, because
math doesn't care how big something is if it's bounded.
I probably should have added an "often" in there. Infinities often make
things more complicated.
> where I'm used to seeing
> unbounded values allowed as a simplifying assumption, and see them as
> common because it's such a powerful tool for allowing general statements
> about whatever branch of math you're considering.
Sure. I didn't mean using infinities in the analysis always makes things
more complicated. I meant using infinities in the problem statement makes
things interestingly complicated, as opposed to problems where everything is
finite, everything halts, etc.
--
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 10/12/2010 6:01 PM, Darren New wrote:
> Kevin Wampler wrote:
>> inputs I'm actually having trouble thinking of a case where this is true
>
> I don't know what "this" you're talking about. Your comments don't make
> sense in the context of the bit you quoted.
>
Yeah, the question I was attempting to ask was only tangentially related
to the bit I quoted (and not very well thought out anyway).
To rephrase, I was wondering if you had any examples of an unbounded
mathematical structure and an associated finite restriction where the
kinds of questions it's "natural" to ask about the finite version are
easier to answer than in the unbounded version? In retrospect,
finite-resource computation is an obvious example you already mentioned,
but I'm having trouble thinking of others.
On a only partially related note, I was reading a blog entry on
mathematical techniques for simplifying problems and ran across the
relevant snipped:
"Make the Objects Really Big: One tool to better understand a problem
that mathematicians use and we rarely seem to is: replace “finite” by
various notions of “infinite.” The study of finite groups is extremely
difficult: one reason is that the interplay between small primes and
each other can be very complex and subtle. Studying instead infinite
groups is not easy, but there are some cases where the theory does
become much easier. For example, studying Lie groups is not easy, but it
does avoid much of the “accidental” number issues that arise in finite
groups. One way to see this is their classification occurred first and
is simpler than the classification of finite simple groups."
I'm not really trying to prove a point with that, but it seemed
interesting and relevant, and is one of the examples I had in mind of a
case where infinities made things easier (hence my curiosity for more
examples of the opposite).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
