RE: Turing vs math

From: Higgo James <james.higgo.domain.name.hidden>
Date: Mon, 25 Oct 1999 09:59:45 +0100

Kolmogorov complexity specifies the simplest UTM-program combination. Again,
the distinction between machine and program is in our minds, and arises
because we are used to PCs.

> -----Original Message-----
> From: hal.domain.name.hidden [SMTP:hal.domain.name.hidden.org]
> Sent: Monday, October 25, 1999 7:17 AM
> To: R.Standish.domain.name.hidden
> Cc: everything-list.domain.name.hidden
> Subject: Re: Turing vs math
>
> Russell Standish, <R.Standish.domain.name.hidden>, writes, regarding the problem
> that different Universal Turing Machines agree on program size only up
> to an additive constant:
>
> > I must admit I had hoped that the "scale factor" issue had been taken
> > into account. I had hoped to chase this up when I got a chance to
> > borrow Li and Vitanyi from the library (requiring the conjunction of
> > the book actually being returned to the shelf, and me taking some
> > holidays). However, my naive approach to the problem is to assert that
> > every UTM can be specified as a program in a "most basic" UTM, which
> > is in itself is simply a transition table in the most basic
> > architecture.
>
> It may be that you are right and that it is possible to define a "most
> basic" UTM. However then you are very dependent upon the specific notion
> of a TM as a way to formalize computation. You have a read/write head,
> you have a tape, you have symbols and states. It is really a very
> arbitrary definition of a computer.
>
> There are other ways to formalize computing: stack machines, register
> machines, cellular automata, even idealized billiard balls bouncing
> around in a giant pinball machine. Each one agrees with the others on
> computational complexity, but again only up to a "scale factor" which
> includes the additive constant.
>
> In other words, for any two of these universal computing models you can
> define a constant C such that the minimal sizes of programs to output a
> given string agree to within C. The problem is that in theory you can
> find universal computing models which differ by arbitrarily large C.
>
> Now, it may be that all computational models which seem intuitively simple
> to us will in fact agree with each other to a large extent and have only
> a small C. The question is whether that means that in fact there is an
> objective definition of the "most basic" model of computation, or whether
> this is something of an artifact of our way of looking at the universe.
> We are limited in our perceptions and ideas, and so maybe it is not
> surprising that all the simple computing models we can conceive are
> ultimately quite similar to each other.
>
> I suspect that it is going to be difficult to identify a subset of all
> computing models which are the "most basic" ones and which can be shown
> to agree on complexity measure within some specific, fixed bound. If we
> could do that it would give a more objective foundation to the concept of
> Kolmogorov complexity (rather than having it be relative to a chosen UTM).
> There would still be some inherent fuzziness, based on the size of
> the bound C, but that would be better than having unlimited fuzziness,
> as I believe is the case in the current theory.
>
> Hal
Received on Mon Oct 25 1999 - 02:30:59 PDT