Re: limitation to the halting proof

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 05/29/04 

Date: Sat, 29 May 2004 08:00:06 GMT

In sci.logic, |-|erc
<gotcha@beauty.com>
 wrote
on Fri, 28 May 2004 21:33:21 GMT
<BeOtc.15211$L.2816@news-server.bigpond.net.au>:
> "The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net>
>> >> >> Working on a similar project, constructing a computer model with a simple UTM.
>> >> >> Some functional computer models are tiny, just a couple lines, and TMs are
>> >> >> trivial, but the smallest UTM is about 20kb. Can't do any models with that
>> >> >> need a 50 byte UTM first, a really primitive notion of computing that a small
>> >> >> mechanical system can emulate. Got close about 5 years ago, had a 2 cell
>> >> >> machine scanning a list for a match for a symbol, almost solved the second
>> >> > <snip>
>> >> >
>> >> > Claudio Baiocchi and Y. Rogozhin each have constructed UTMs with
>> >> > a two-symbol alphabet and 22 states.
>> >>
>> >> That does sound rather pretty. :-) Of course it doesn't do much
>> >> for |-|erc's halting problem.
>> >>
>> >
>> > that's your halting problem remember not mine, you're the one
>> > diagonalising at every opportunity claiming sequences are
>> > imaginary and invisible numbers are real.
>>
>> Numbers are invisible. Or have you ever seen a "2"?
>> All you've seen are lit pixels in the shape of a "2",
>> darkened spots on paper in the shape of a "2", strips or
>> threads of fabric woven in the shape of a "2", ...
>>
>> Of course one sees pairs of things all the time -- but
>> that's not the same thing.
>>
>> As for the sequence of functions provably halting: that's
>> constructible and can be proven to be a valid sequence.
>> Trouble is, it's not complete.
>>
>> Unless you can prove the Collatz Conjecture...?
>
> no you're flying off on tangents at every turn like always.
> that's a simulation nothing to do with haltability, just
> rephrase the problem as does it halt in x cycles?

Different question. The question "does it halt in X cycles"
is always solvable -- just run the UTM for X cycles and
if it's halted, that's it, and if not, that's it too.

The question "does it eventually stop" is not. The Collatz
Conjecture is a pretty conjecture, which no one has proven
to eventually halt yet. Until they do, it makes for a
mildly interesting counterexample.

>
> you claim the uncountable irrationals are not able to be put on
> paper as opposed to 2, that they go 'inbetween' the numbers we
> can *write* hence *see*. you use a faulty premise of open
> diagonalisation and when its shown to be nonsense you shift
> the burden.

I've yet to see a working proof that it's nonsense. Granted, every
number we ever write down, every number we think of, ever number
we work with in the practical world is in fact rational, given
the nature of floating point arithmetic in modern computers and
the simple finiteness of the representations used. Or, they are
symbolic algebra -- e.g., "sqrt(2)" -- which we can manipulate
using various rules (sqrt(2)^2 = 2, sqrt(2) + sqrt(2) = 2*sqrt(2),
sqrt(2) / sqrt(2) = 1). pi and e are also interesting transcendentals
which we discuss symbolically; there's a few others.

Or, if one wants to get ridiculous and write down a number on
every atom in the Universe that one can see from the Earth,
one only has so many atoms, regardless of representation.

> you have no mathematical opposition to countable functions and
> countable reals is just a step further. UTM(n), from n e N IS
> the countable reals, it doesn't miss a beat, not all n halt thats
> a petty copout requirement of YOUR argument, now even that is invalid.

It's not even countable. It's finite. Of course mathematics does
not always deal in the concrete and the graspable -- one interesting
question is whether the digit expansion of pi is normal, for
example. Of course pi's digit expansion can never be written
down in full, which means we have to talk about something that
is by necessity incomplete.

But mathematicians do that all the time. N = {1, 2, 3, ... }
for example, has more than 3 elements, and most people infer
that N = {1} union {x + 1: x in N} [that's two Peano axioms
right there] solely from this representation. Of course one
can be led astray: e = 2.718281828... occasionally confuses
people into thinking e is rational, when it's not (the next
three digits are "459").

So we are forced to talk about a set R whose elements we can
never write out in full, exhaustively list, or compute using
a UTM, even were we to run said UTM until the heat death of
the Universe (current theory suggests about 50 billion years
or so).

In any event, Cantor has *two* proofs. The first proof relies
on R having no gaps between numbers, no matter how one
cuts them. [*]

http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof

The second is the diagonalization proof:

http://en.wikipedia.org/wiki/Cantor's_diagonal_argument

Both have the same problem, in that they rely on talking about
infinite things without explicitly writing them out in full.
But that doesn't mean R is countable; it merely means that
the subset of R that humans are going to encounter is.

One part of this subset might be construed as all numbers q
representable by the schema

q = n * 2^m

where 2^k <= n < 2^(k+1) for some k, and m is a bounded
integer (which can be positive or negative). [+] All of these
are rational and the cardinality of the set of all such
numbers is finite -- less than 2^64, in fact, in current
computer implementations. Arithmetic operations on these
numbers are sufficiently corrupted so that the result is
also within the set; this can lead to some goofy inaccuracies.
For example, 3.11 - 3.10 = 0.00 if one isn't careful
at representing the subtraction result, which is close to
but just shy of 0.01. (Win95's calculator is famous for
this goof.)

>
> Herc
>

[*] Q does not have this property. If one defines a set
    A: {x <= 0 or x^2 < 2} and another set
    B: {x > 0 and x^2 > 2}, then it's clear that
    for any a in A, it's less than any b in B, but
    one cannot find a c in Q such that a < c < b
    for all a in A and all b in B. Of course c = sqrt(2)
    in R does fine, and c turns out to be in neither A nor B.
    Most proofs assume c = d/e for some relatively prime d
    and e, then derive the contradiction that d and e must
    both be even.

[+] There are some adjustments to this definition to include
    0, infinity, and the special token "not-a-number" (NaN);
    NaNs in particular are the result of divisions by 0
    or logarithms of negative numbers, among other things.
    Infinity merely means the operation resulted in a number
    that was too big. 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages

  • Re: limitation to the halting proof
    ... there are also rules for manipulating INFINITE ... one only has so many atoms, regardless of representation. ... DEFINE what YOU mean by "countable reals". ... the UTM takes TWO n's as arguments. ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is incorrectly formed
    ... > Okay fine, then the Halting Problem is solvable because the proof is flawed. ... Note that we can construct D *if* the TM HALT exists. ... But now what happens if we run D on (a representation of) itself. ...
    (sci.logic)