Re: Universal turing machine applied to itself?

On Oct 30, 8:19 am, LauLuna <laureanol...@xxxxxxxx> wrote:
On Oct 30, 5:20 am, Rotwang <sg...@xxxxxxxxxxxxx> wrote:

On 30 Oct, 01:22, dwwdkddb <kimfier...@xxxxxxxxxxx> wrote:

By proper encoding and enumeration of inputs and instructions, one may write T_n(m) to denote the result (if it exists, i.e., if the machine halts) of the n-th Turing-machine acting on the m-th input. Now let U be a universal Turing-machine. Then U is itself the u-th Turing-machine, for some u; so U = T_u. But what's T_u(u)? I've been agonizing over this question for days now. Can someone please help? Thanks in advance!

I don't know any more about this kind of thing than what I have read
in popular accounts (ptui!), but my understanding is that a universal
Turing machine really takes two inputs, namely the number of the
Turing machine it is to simulate and the input with which that Turing
machine is to be run. Thus implicit in any universal Turing machine
which takes one input is some method by which one represents the
number of the instructions and the number of the input as a single
number. Since there are many different such methods which will give
different answers, my guess would be that T_u(u) will not have a
particularly "nice" interpretation.

As Klueless says, T_u has to receive a pair <m,i> as input. But we can
code <u,u> as u. If so, T_u(u) loops.

This is a way of proving Turing's 1937 theorem (the undecidability of
the halting problem): T_u(u) loops, so it doesn't stop and tell us
that it loops.

Think of the 'constructive' way in which TM's behave. T_u, when fed
with <m,i>, decodes m and proceeds to compute T_m(i). So, the
computation of T_u<m,i> is determined by the computation of T_m(i).

Now, for T_u(u) it happens that T_u should decode u and proceed to
compute T_u(u). So, the computation of T_u(u) would be determined by
itself; this circularity makes T_u loop.

Regards

How about, a different language for the Turing machine.

Instead of Godel numbering in arbitrary ways with random integers for
each syntactic element in linear order, instead have multiple levels
and make a code to minimally represent the transition diagrams
(graphs, with labelled vertices and edges). Combinatorially enumerate
them. Think of recursive relations as reactions, descriptions of rate-
of-change problems. Make them the background lattice

Then, those are much more usable as finite automatons. Then, figure
out more about how they're encoded by a Turing machine. Also, one of
those automatons represents a subset, as does the infinite tape (of
all of them). Imagine how they tile and pattern the space, defined by
all the Turing machines, then measure distance in the space.

Then maybe there are some tests on the different kinds of automatics,
in the various naturally coded languages, automata, for very small
classes of automata, and very few of them.

There should be clear stable results by simply zeroing complex terms.
The idea is to have a field that is those automata, then, that's the
input. So, then the results of functions over those terms is
precomputed, crude approximation.

Seriously, if the internal coding of natural languages was defined it
would be in those terms. Half of the integers are even.

In the proper coding, there are many intermediate languages of
structurally enumerated terse expressions.

Then, in aggregate media, integrate.

That'll help you.

Ross

--
Finlayson Consulting

.

Relevant Pages

  • Re: Turing Machines and Physical Computation
    ... Turing Machine was originally described independently but equivalently by ... It is widely -- and incorrectly -- held that a Universal Turing Machine can ... the class of finite automata is set apart by the fact that they may ... which may write any of an infinite set of binary strings on ...
    (sci.math)
  • Re: Turing Machines and Physical Computation
    ... Turing Machine was originally described independently but equivalently by ... It is widely -- and incorrectly -- held that a Universal Turing Machine can ... the class of finite automata is set apart by the fact that they may ... which may write any of an infinite set of binary strings on ...
    (comp.theory)
  • Re: Consciousness, Mind, Matter, Meaning and Information
    ... Neil W Rickert wrote: ... is something applied to automata, not to languages. ... that can be calculated with a Turing Machine, ...
    (comp.ai.philosophy)
  • Re: Election 2008 for computer programmers
    ... their languages are recognised by finite state automata. ... nothing "after" a Turing machine: in fact, the book took pains to show ... The point is we need to understand politics at a higher level ...
    (comp.programming)
  • Re: Election 2008 for computer programmers
    ... their languages are recognised by finite state automata. ... nothing "after" a Turing machine: in fact, the book took pains to show ... based on your higher and more recent knowledge to post correct ... You need to qualify it with the fact that you made it up. ...
    (comp.programming)
Quantcast