Re: In a Bad Mood
From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 06/10/04
- Next message: Sander Bruggink: "Re: Alan Turing's Halting Problem is incorrectly formed"
- Previous message: The Ghost In The Machine: "Re: Alan Turing's Halting Problem is incorrectly formed"
- In reply to: Chairman of the Ozzy Osbourne Appreciation Society: "Re: In a Bad Mood"
- Next in thread: Barb Knox: "Re: In a Bad Mood"
- Messages sorted by: [ date ] [ thread ]
Date: Thu, 10 Jun 2004 08:00:11 GMT
In sci.logic, Chairman of the Ozzy Osbourne Appreciation Society
<mathgeek42@hotmail.com>
wrote
on Wed, 09 Jun 2004 17:13:50 GMT
<izHxc.1859$IO.1850918@news4.srv.hcvlny.cv.net>:
> The Ghost In The Machine wrote:
>> In sci.logic, |-|erc
>> <gotcha@beauty.com>
>> wrote
>> on Mon, 07 Jun 2004 22:03:57 GMT
>> <hD5xc.17257$rz4.8931@news-server.bigpond.net.au>:
>>
>>>>>How many integers are there?
>>>>>How many (leading) digits of anti-diag appear on the countable
>>>>>infinite list of computable numbers?
>>>>>
>>>>>clue : its the same answer ;-)
>>>>>Herc
>>>>>
>>>>
>>>>http://www.cs.nyu.edu/pipermail/fom/2001-September/005071.html
>>>>
>>>>suggests one, although because of the "n = +oo" problem it
>>>>may not be palatable.
>>>>
>>>>Another variant is Chaitin's Constant (represented by capital omega,
>>>>apparently). This should probably be referred to as Chaitin's
>>>>Construct, as it is highly dependent on the subsystem over which
>>>>it reigns (and the alphabet allowed on the tape), whether it be
>>>>Turing Machines, indefinite-register/indefinite-value machines,
>>>>or other such.
>>>>
>>>>http://mathworld.wolfram.com/ChaitinsConstant.html
>>>>
>>>>This is not quite as affected by the "n = +oo" problem.
>>>>
>>>>Still another non-computable item is physical: determining
>>>>whether a given atom will decay, and when.
>>>>
>>>>As for the number of integers: that's equal to the number of reals,
>>>>as far as the computables are concerned. Both are finite (though
>>>>huge); there are only so many atoms in the Universe...
>>>>
>>>
>>>
>>>are you answering the 2 questions? try it like so.
>>>
>>>Answer 1 :
>>
>>
>> Real: Indeterminate but finite.
>>
>> Abstract: Aleph-null.
>>
>>
>>>Answer 2 :
>>
>>
>> The operation does not scan as all computable numbers are rational.
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> Hmmm, are you sure about this? Based on the definition
> I've seen, the rationals are a proper subset of
> computable numbers.
>
It may depend on how one defines computable. I'll admit I'm
not entirely sure myself, but one reasonable method of
"computable" is "standard digit expansion form, writable in
finite time by a Turing Machine".
By necessity, all such numbers have to be rational, as
they're multiples of a power of 10. (Or, if one wants
a little more flexibility, a base b where b is a positive
integer agreed upon beforehand. b = 1 is treated as a bit
of a special case [tally marks]; all others are more or
less handled in the usual fashion.)
Of course, if one wants to get sophisticated, one can
include symbols such as pi, e, and sqrt(2), and then try to
figure out whether expressions such as pi + e are rational
("is pi+e in Q?" turns out, apparently, to be an unsolved
problem, surprisingly!), computable (it probably is, since
pi and e are approximatable using fairly simple formulas
to any desired degree of accuracy), or both.
I've used the term "semi-computable" in the past to
describe a number which can be approximated by a computable
Cauchy sequence or whose digits can be computed by a Turing
machine (which never halts, but just keeps writing digits)
or equivalent computational method. I'm not sure I like
the term (and rather doubt I really did invent it, as
the concept is extremely obvious) but can't think of a
better one.
In any event, there are only finitely many numbers that can ever
be written out; there is only so much carbon in the Universe. :-)
It gets more problematical. As far as I can tell there are only
a countably infinite number of Turing Machines, as one can
encode the transition functions into a proper subset of the
natural numbers. Some of these will halt (we can't tell which
ones) and produce computable numbers. Others will keep spitting
out digits. However, because there are only countably many,
the numbers in the rest of R cannot be computed.
-- #191, ewill3@earthlink.net It's still legal to go .sigless.
- Next message: Sander Bruggink: "Re: Alan Turing's Halting Problem is incorrectly formed"
- Previous message: The Ghost In The Machine: "Re: Alan Turing's Halting Problem is incorrectly formed"
- In reply to: Chairman of the Ozzy Osbourne Appreciation Society: "Re: In a Bad Mood"
- Next in thread: Barb Knox: "Re: In a Bad Mood"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
