Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: You pedantic ignoramuses
Replies: 25   Last Post: Jan 16, 2005 12:01 PM

 Messages: [ Previous | Next ]
 |-|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

Date Subject Author
1/13/05 |-|erc
1/13/05 anonymous
1/13/05 |-|erc
1/13/05 The Ghost In The Machine
1/13/05 |-|erc
1/14/05 The Ghost In The Machine
1/14/05 |-|erc
1/14/05 The Ghost In The Machine
1/14/05 |-|erc
1/15/05 The Ghost In The Machine
1/15/05 |-|erc
1/15/05 The Ghost In The Machine
1/15/05 |-|erc
1/16/05 The Ghost In The Machine
1/16/05 |-|erc
1/16/05 David Bernier
1/16/05 |-|erc
1/16/05 David Bernier
1/16/05 David Bernier
1/16/05 |-|erc
1/16/05 The Ghost In The Machine
1/16/05 |-|erc
1/16/05 The Ghost In The Machine
1/15/05 Daniel Grubb
1/15/05 The Ghost In The Machine
1/15/05 Rupert