Re: The Modified Halting Problem, Take ??? .

Stephen Harris wrote:
R. Srinivasan wrote:
Note that Chaitin's Omega is an example of a real number that is not
computable by a (classical) TM, but for which every rational
approximation is computable. So the second example I gave, with
infinitely many halting TMs, does apply to Omega and will indeed
compute rational approximations of Omega successively (one at a time),
to arbitrary accuracy-- correct me if I am wrong here. But this does
not make Omega computable -- there is no non-halting TM that will
compute every digit of Omega. So the two cases are, by conventional
wisdom, deemed to be qualitatively different.

Well, I do know that they compute Omega to some finite number of
digits before it doesn't go further. I don't really know the reason
maybe more approximation is possible but it becomes intractable.

Omega is Delta_2 or "trial and error computable". This means that there is a Turing machine M such that when M is run (on empty input, say)

1) If the nth bit of Omega is 1, there is a step t after which 1 will
remain forever on the nth block of M's tape
2) If the nth bit of Omega is 0, there is a step t after which 0 will
remain forever on the nth block of M's tape

but there is in general no effective method of determining whether or not M has settled on the nth bit of Omega, or whether it will change it later. Notice that 1 and 2 guarantee that the computation has a well-defined "limit", namely

0.r_1r_2r_3... where r_i = 1 if the ith block on M's tape eventually
settles to 1, and 0 if the ith block on M's tape eventually settles to
0

which is just Omega, by 1 and 2.

--
Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
.

Relevant Pages

  • Re: does sqrt(2) exist in CM?
    ... |>| There is an approximation procedure for Omega. ... | it doesn't allow *explicit* construction of arbitrarily good ... | or EXPLICIT definability, ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... help explain why Omega may be regarded as nonconstructible, ... assuming that the approximation ... or presentable as mental constructions. ... be regarded as nonconstructibile. ...
    (sci.math)
  • Re: The Modified Halting Problem, Take ??? .
    ... infinitely many halting TMs, does apply to Omega and will indeed ... compute rational approximations of Omega successively, ... maybe more approximation is possible but it becomes intractable. ... uncomputable, not even one digit. ...
    (sci.logic)
  • Re: does sqrt(2) exist in CM?
    ... >>| There is an approximation procedure for Omega. ... >> a computable sequence of rationals, ... but at no step is such an approximation ... or presentable as mental constructions. ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... >| There is an approximation procedure for Omega. ... it doesn't allow *explicit* construction of arbitrarily good ... or EXPLICIT definability, ...
    (sci.math)