|-|erc
Posts:
1,782
Registered:
1/25/05
|
|
Re: You pedantic ignoramuses
Posted:
Jan 16, 2005 6:25 AM
|
|
-------------------------------------s-o-s------------------------------------
"The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote in
> >> >> > lets pull a function out of the air, R(x) = Comp(random, x) + 1 mod 10
> >> >> >
> >> >> > according to you, this LIARS statement F(x) = ~F(x) is
> >> >> > a new random sequence and proves the set of all programs
> >> >> > Comp can't spit out any random string at all.
> >> >> > Herc
> >> >>
> >> >> Without knowing (or finding earlier implementations of) Comp(x,y), I
> >> >> can't process this statement. I can of course assume that
> >> >> Comp(x,y) is machine x running on input y, in which case the correct
> >> >> equality
> >> >>
> >> >> R(x) = (Comp(x,x) + 1) mod 9
> >> >>
> >> >> and that is indeed a new sequence, not in the Comp() list. Of
> >> >> course, it is not a computable sequence, though it is well-defined.
> >> >
> >> > Is R computable?
> >>
> >> If you're asking whether every r in R is computable, the
> >> answer is no. Chaitin's Constant is a nice counterexample.
> >>
> >> Besides, the set of computable reals is of measure 0,
> >> since the machines computing said reals can be mapped 1-1
> >> with the integers. Since R is obviously not measure 0,
> >> there are uncomputable reals. (Presumably, a real is
> >> computable if there exists a TM that can spit out its
> >> digits. There are admittedly a few technical issues, such
> >> as which part of the tape can be used for digit-spitting,
> >> and which for scratchwork. In a pinch, one can use two
> >> tapes; TM2 can be mapped to TM by mangling the states and
> >> changing the alphabet, so one merely simplifies the problem
> >> thereby; the number of computable reals is unchanged.)
> >
> >
> > We'll use a more global defn of computable. Computable means
> > computable in some computer system.
>
> Turing machines can compute anything a modern PC can compute.
> It just takes more cycles. :-)
>
> >
> > Say you have an OS on your computer that runs two languages L1 and L2.
> > Each language has its own UTM.
> >
> > In L1, you output a stream of computable numbers, c1, c2, c3...
> > (oo many digits isn't as big as it used to be!).
>
> Erm...yeah.
>
> >
> > The OS pipes the result to a program in L2, this program then outputs
> > R(x) = UTM-L1(x,x) + 1 mod 9.
> >
> > Same effect as munging tapes, and the diag is computable in L2.
> >
> > (note this goes against my default argument of forming diagonals
> > being an invalid op.)
>
> But forming diagonals *is* an invalid op in some contexts,
> as L2 is a finite system. In short, if UTM(x,y) computes a
> set of numbers S, then the diagonal number D is not going
> to be computable as one gets into the "infinite thread"
> problem.
>
> This is not a problem for mathematicians, though; most
> (read: all but measure 0) reals are not computable.
that's a false sense of security thinking you can define functions
that wont parse on computer, you boys like to talk big...
but in this case you are safe.
real digit
1 1 2 3 4 5 6 7
2 / / / /
3 / / /
4 / /
5 /
6
7
L1 can send an infinite stream of reals like so.
L2 gets the reals and can COMPUTE an antidiag, on a real computer.
>
> >
> >
> >>
> >> Of course, there are also computable reals: sqrt(2),
> >> pi, and 1/3 are perfectly computable. One can also get
> >> into complexity space, asking questions such as how much
> >> time and storage might be needed to compute sqrt(2), pi,
> >> and 1/3. But this is a detail.
> >>
> >> And then there's TX_10 = {k/10^n: n >= 0, n, k in J}.
> >> This is a perfectly computable and denumerable set,
> >> consisting of all finite prefixes (base 10). It is dense,
> >> but does not cover R or Q.
> >>
> >
> > If TX_10 was personified it would be dense indeed.
>
> Does TX_10 cover R? The answer is no. If you wish
> to dispute this, show proof otherwise.
TX_10 will mark every position of the number line, drawing it black,
but I'll allow you some claim on the terminology, it doesn't cover R.
Herc
|
|
