 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>
> I don't know much about the formal theory of computation though. I
> always assumed that "computable function" just meant "function that can
> be computed by a computer". Apparently the definition is much less
> general that than...
>
Not really! Formally you tend to consider only functions which take a
single natural number as input and provide a single number as output.
This may seem restrictive, but remember that everything on your computer
can be considered as being as represented by integers (in binary)
anyway, so it's not really a restriction at all.
As for the `function' part of `computable function' you of course mean
something which only takes an input and provides an output, and thus
doesn't allow for user interaction and the such, but you can always
model user interaction as simply providing the inputs to a an
appropriately defined proper function so even this isn't really a
restriction.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> What is more unintuitive is that the amount of rational numbers is the
> same as the amount of integers.
What is unintuitive to me is that if you draw a numberline on the wall
and toss a dart at it (figuratively speaking), your probability of
hitting a rational number is zero. That is, there are so many more reals
than rationals that the chance of picking a real that's rational at
random is literally zero. It would seem there's *some* epsilon chance,
but apparently not. :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] san rrcom> wrote:
> What is unintuitive to me is that if you draw a numberline on the wall
> and toss a dart at it (figuratively speaking), your probability of
> hitting a rational number is zero. That is, there are so many more reals
> than rationals that the chance of picking a real that's rational at
> random is literally zero. It would seem there's *some* epsilon chance,
> but apparently not. :-)
Yet between any two chosen real numbers there's an infinite amount of
rational numbers, and vice-versa. There's no range of real numbers where
there wouldn't be an infinite amount of rational numbers.
Yet there are "more" real numbers than rational numbers.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 21:00:36 +0100, Orchid XP v8 wrote:
>>> always assumed that "computable function" just meant "function that
>>> can be computed by a computer".
>>
>> Yes. But the question is, what functions *are* computable by a
>> computer? That's kind of the point.
>
> The question, surely, is what functions are *not* computable by a
> computer? ;-)
I would think any problem that was mathematically intractable. :-)
Or put another way, some computational problems where the growth function
is exponential. Some of those problems are solved on a small scale
computationally (like the traveling salesman problem), but as the scale
of the problem grows, the complexity grows as well.
At least that's what I remember from my discrete maths class in the early
90's. :-)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 20:59:40 +0100, Orchid XP v8 wrote:
> Proving that something exists is a *comparatively* easy task: Just hold
> up one of them, and the fact that you're standing there holding it kinda
> proves it exists.
Depends on the nature of the proof. Try taking that argument to someone
with a background in philosophy. :-)
"My universe is what happens to my eyes and my ears; anything else is
surmise and hearsay."
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> ...OK, and this is the kind of thing that I sit down and read and end up
> feeling utterly perplexed.
>
> Logic, set theory, category theory, number theory, complexity theory,
> topology... they all seem to abound with utterly counter-intuitive laws
> and theorums. It's really quite mind-bending.
Don't be intimidated, I think that the diagonalization arguments are
actually rather easy to understand for someone who doesn't have a lot of
background in this sort of thing. It's a bit mind blowing at first, but
at some point it'll click and everything will make sense, something
which I haven't found to be the case with eg. set theory.
I suggest you start by proving that there's the same number of rationals
as natural numbers. Once you've done that study Cantor's diagonal
argument until you understand why there's more reals than natural
numbers, and thus more reals than rationals. Ask for help if you're
confused and I'll provide it when I read the newsgroup (or more likely,
someone else will beat me to it).
From there I'd take a look at the definition of the busy beaver
function as an example of the same sort of technique on computable
functions, and then look at the halting theorem in the same light.
Sooner or later it should all start to seem intuitive and
straightforward, even if it's a bit mind-bending at the moment.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> The question, surely, is what functions are *not* computable by a
>> computer? ;-)
>
> I would think any problem that was mathematically intractable. :-)
Well, if you don't know "how" to solve a problem then you can't write a
program that does it. That's true enough. I'm not sure it makes it not a
"computable function" though...
> Or put another way, some computational problems where the growth function
> is exponential. Some of those problems are solved on a small scale
> computationally (like the traveling salesman problem), but as the scale
> of the problem grows, the complexity grows as well.
>
> At least that's what I remember from my discrete maths class in the early
> 90's. :-)
Nope. That's not "impossible" to compute, just really damned slow. ;-)
To a mathematician, 10^1534 years is a finite amount of time. In
practical terms it's a ridiculously long time - many times longer than
the current age of the universe, and plenty long enough for any
hypothetical computer to exhaust all the available energy in the
universe without reaching the end - but still, technically, a finite
run-time.
If we're talking about what a computer can *theoretically* calculate.
It's just a matter of leaving the machine running for long enough.
But even given infinite time and memory, a computer *still* can't solve
the Halting Problem though. Even theoretically. Don't ask me why...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> What is unintuitive to me is that if you draw a numberline on the wall
> and toss a dart at it (figuratively speaking), your probability of
> hitting a rational number is zero. That is, there are so many more reals
> than rationals that the chance of picking a real that's rational at
> random is literally zero. It would seem there's *some* epsilon chance,
> but apparently not. :-)
Probability of hitting an object with a size of zero: 0%. ;-)
Probability of hitting an uncountable infinity of objects each with a
size of zero: 100%.
GO FIGURE!
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 13:09:40 -0700, Kevin Wampler wrote:
> I suggest you start by proving that there's the same number of rationals
> as natural numbers.
*ding* - light bulb just went on here. I was trying to figure this one
out, and it just intuitively appeared to me.
The weird thing is that I can't even explain it, but I understand it.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> I suggest you start by proving that there's the same number of rationals
> as natural numbers.
But there are surely *more* rational numbers than natural numbers?
Actually, let's try something easier: Common sense tells you that the
number of 2D coordinates is obviously [vastly] greater than the number
of 1D points. Yet set theory asserts that both sets are exactly the same
size. How can this be?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
