strange warning

[Joe Pfeiffer]

There is no such thing as a "universal Turing machine", though the term
is sometimes used - a Turing machine is unlimited, so there is no need
for a "universal" one. Conversely, one could talk about a "finite
Turing machine" with a limited memory.

This is terminology I have encountered, and (I think) he means the same
thing by it as I've seen -- a UTM is a TM which takes as input an
encoding of a TM and that TM's input, and emulates that TM on that
input.

 

[Ben Bacarisse]

Turing's universal machine he called "u". U takes quintuples, in a certain
order, that specify another Turing machine, so that the first entry in
the quintuple represents the current state, the second entry the symbol
on the tape, the third entry the symbol to write to the tape, the fourth
entry the direction to move the print head, and the last entry the state
to put the machine into.

You do know that I know this stuff, yes?

Now let's call that machine U(T), because it's Turings.

Personally, I'd use a subscript (U_t in ASCII) but why give it another
name? As you've said it's already got a name, Turing called it U. Why
give it another?

Now let's imagine that we have a similar machine, which is exactly the
same as U(T), except that the first entry and the second entry are
transposed.

What entries? The only use of the term so far is in your description of
a valid input for U (or U(T) as you also want to call it), but U has no
"entries" to swap -- it's just a TM, not a TM plus some specific input tape.

It should be obvious that if we run U(2) on input designed
for U(T), it won'e emulate the same Turing machine as U(T), but if
we run U(2) on input designed for U(T), with the column transposed,
we will get the same Turing machine.

Ah, you mean that U(2) is a universal TM that expect differently ordered
input. You made very heavy going of saying that.

It should also be obvious that we can specify U(T) in U(2) format. When
we run U(2) on this, it emulates U(T), it then emulates any Turing
machine.

So? If U is universal, U(2) will be too, and there are much simpler
proofs of that fact. Students of TMs learn about computable reductions,
from which you get simpler proofs, together with a body of results that
can be combined to answers lots of questions like this.

Now let's transpose columns 2 and 3, and do the same thing. Let's call
this machine U(3). U(3) can also emulate U(T). But there's an infinite
number of transformations we can apply to Turing's data format,
so an infinite number of machines which, fed the appropriate input,
will emulate U(T).

So what? There is a staggering simple proof of this fact, if you really
want to prove it, but why would you?

So how to we know that a machine is in U, that is, that there is sequence of
bits which, when we feed it, will allow it to emulate U(T)? Obviously you
can prove it in many cases by showing that the machine has a sub-graph
which is U(T), You can prove it in others by showing that there is a bit
sequence which puts it into U(T) emulation mode. But you can't show that
there is no such sequence by running it, and you can't analyse its state
graph except by running it.

See Rice's theorem -- a much better way to get to the fact that the set
of universal TMs is not TM-decidable.

So I don't know if there's a minimum criterion for which we can say
"this state graph isn't rich enough for U", I can't describe the
minimal machine in U.

I won't go there. I suspect far too many M-words.

Now, does any of this answer my question about why you are pontificating
about this? I wanted to close the technical discussion off, but I was
curious about why you thought you should post about this stuff.

 

[Joe Pfeiffer]

If I recall correctly, I have simplified things. The famous paper was,
I think, published twice. Turing's PhD advisor was Alonzo Church, but
he only went to Princeton after the paper was in a final draft. The
version you see in facsimile all over the web is a revision with the
addition of things like the equivalence with the lambda calculus added.

Ah, OK -- it was still a *lot* faster than I'd known.

You got me curious, so I found the paper last night. Reading it now...

 

[Malcolm McLean]

Now, does any of this answer my question about why you are pontificating
about this? I wanted to close the technical discussion off, but I was
curious about why you thought you should post about this stuff.

Basically because instead of agreeing that all computers are Turing machines, and
therefore all programming languages are basically the same, people asked for
endless justifications, elaborations, and so on of the statement.

I'm not a particular expert in Turing machines. I know the basics, but largely as
communicated knowledge rather than trying to go to first principles and
prove everything. A computer is a Turing machine, however. You know that,
I know that, but not everyone knows that, or at least didn't at the start
of the discussion.

I don't know how to describe the minimal universal Turing machine. Maybe
someone does. That's far from "pontificating".

 

[Keith Thompson]

On 05/16/2014 10:59 AM, Martin Shobe wrote:
...

More precisely, "All squares are square".


I'm in full agreement.

Perhaps they're McLean-identical.

 

[Ben Bacarisse]

Basically because instead of agreeing that all computers are Turing
machines, and therefore all programming languages are basically the
same, people asked for endless justifications, elaborations, and so on
of the statement.

Yeah, tell me about it. People should just learn to accept what you
say. If you say it's a fundamental theorem of computer science then it
is. Why can't people just accept that instead of asking for reasons or
references and such?

So what if what you meant was not an *actual* theorem in the tediously
pedantic sense (you know, with a name and all that), and maybe you don't
mean *all* programming languages, just the ones that are all equivalent
to each other, but the gist of it, that all of *those* ones are all
equivalent, *is* a fundamental theorem of computer science (or will be
when someone gets round to giving it a name).

I'm not a particular expert in Turing machines. I know the basics, but
largely as communicated knowledge rather than trying to go to first
principles and prove everything. A computer is a Turing machine,
however. You know that, I know that, but not everyone knows that, or
at least didn't at the start of the discussion.

At least you were on hand to clear up any confusion.

I don't know how to describe the minimal universal Turing machine. Maybe
someone does. That's far from "pontificating".

No, quite. There's stuff you don't know are not afraid to say it! How
could anything you say come over as if you were laying down the law?

 

[Malcolm McLean]

No, quite. There's stuff you don't know are not afraid to say it! How
could anything you say come over as if you were laying down the law?

Exactly. When I do know something I'm firm. When I don't, I'm happy to
admit that maybe someone else can come in.

Now there are four Turing machines with a single state. It's intuitively
obvious that none of them are in U, there's no sequence of bits you can
feed to a single state Turing machine which makes it emulate U(T).

But what about the three state machines? Can anyone prove that the
same is true of the three state machines? How would you set about
doing that? I genuinely don't know. There are limits to my knowledge.
I am not pontificating, and anyone else is more than welcome to
weigh in.

 

[Ben Bacarisse]

(the snipping may have left it less than obvious that my post was
entirely sarcastic, so it bears saying so here)

Exactly. When I do know something I'm firm. When I don't, I'm happy to
admit that maybe someone else can come in.

I note the "maybe" -- what a delightful detail that is.

Now there are four Turing machines with a single state.

Really? What are they?

It's intuitively
obvious that none of them are in U, there's no sequence of bits you can
feed to a single state Turing machine which makes it emulate U(T).

But what about the three state machines? Can anyone prove that the
same is true of the three state machines? How would you set about
doing that? I genuinely don't know. There are limits to my knowledge.
I am not pontificating, and anyone else is more than welcome to
weigh in.

Why? This c.l.c. Correcting errors is one thing, but answering
diversionary questions is really not on. Ask in comp.theory -- it's a
well-explored field (and don't forget to tell them about the Turing
equivalence theorem).

 

[Malcolm McLean]

Really? What are they?

machine 1
in state 1: on bit 0 : write bit 0: forwards : goto state 1
in state 1: on bit 1 : write bit 0: forwards : goto state 1

machine 2
in state 1: on bit 0 : write bit 0: forwards : goto state 1
in state 1: on bit 1 : write bit 1: forwards : goto state 1:

machine 3:
in state 1: on bit 0 : write bit 0: forwards: goto state 1:
in state 1: on bit 1 : write bit 0: backwards: goto stare 1

machine 4:
in state 1 n bit 0: write bit 1: forwards: goto state 1
in state 1 n bit 1: write bit 0: backwards: goto state 1

I think that's it. Aren't all the others symmetrical?
Wipe out, pass over, stick, and beetle.

Maybe someone's got another.

Why? This c.l.c. Correcting errors is one thing, but answering
diversionary questions is really not on. Ask in comp.theory -- it's a
well-explored field (and don't forget to tell them about the Turing
equivalence theorem).

Topics are allowed to drift a bit.
If someone can give an example of a 3 state universal Turing machine,
then that's also the minimal C compiler, for example.

 

[Ben Bacarisse]

machine 1
in state 1: on bit 0 : write bit 0: forwards : goto state 1
in state 1: on bit 1 : write bit 0: forwards : goto state 1

machine 2
in state 1: on bit 0 : write bit 0: forwards : goto state 1
in state 1: on bit 1 : write bit 1: forwards : goto state 1:

machine 3:
in state 1: on bit 0 : write bit 0: forwards: goto state 1:
in state 1: on bit 1 : write bit 0: backwards: goto stare 1

machine 4:
in state 1 n bit 0: write bit 1: forwards: goto state 1
in state 1 n bit 1: write bit 0: backwards: goto state 1

I think that's it. Aren't all the others symmetrical?
Wipe out, pass over, stick, and beetle.

Maybe someone's got another.

Everyone who knows anything about TMs should have "another". What is
striking here is how little you are aware of your lack of understanding.
You seem to know the definition of a TM, but you don't seem to
understand much about the consequences of that definition. None the
less, you are happy to pontificate about what is and is not a
fundamental theorem of computer science.

(The names are nice touch. They suggest that the four machines are so
obviously no more than four that they even have cute names.)

<snip>

 

[Malcolm McLean]

Everyone who knows anything about TMs should have "another". What is
striking here is how little you are aware of your lack of understanding.
You seem to know the definition of a TM, but you don't seem to
understand much about the consequences of that definition. None the
less, you are happy to pontificate about what is and is not a
fundamental theorem of computer science.


(The names are nice touch. They suggest that the four machines are so
obviously no more than four that they even have cute names.)

I was surprised at that.
My reasoning was 3 1 bit states, 8 possible machines, but 1 and 0
have no inherent meaning, so divide by two.

 

[Malcolm McLean]

I was surprised at that.
My reasoning was 3 1 bit states, 8 possible machines, but 1 and 0
have no inherent meaning, so divide by two.

I've got it.

8 possible instructions, each machine needs two of them, but is
restricted to a 1 or a 0 in field 1. So how many does that give us?
1 selection from four, then another selection from 4, = 16, divide
by 2, so it's 8 machines.
That's where I went wrong.

in state 1: on bit 0: write bit 1 : forwards: goto state 1
in state 1: on bit 1: write bit 0 : forwards: goto state 1

that will invert the bits, so let's call it "invert". I thought it was just
the mirror image of passover, because it adds no information content,
but actually maybe it isn't.

in state 1: on bit 0: write bit 0 : forwards : goto state 1
in state 1: on bit 1: write bit 1 : backwards : goto state 1

what will this one do? It chugs forwards until it hits a set bit,
ten goes forwards and backwards. So that's "stick". The one I called
"stick" is actually "glitch", it's like wipe out, but with a
little wobble when it hits a set bit. So another mistake.

So there should be two more. I'll be back later.

 

[Malcolm McLean]

On 5/16/14, 11:20 PM, Malcolm McLean wrote:

How about:

in state 1: on bit 0: write bit 1: forwards: goto state 1
in state 1: on bit 1: write bit 0: forwards: goto state 1

My nickname would be "invert"


(I suppose it depends on what you call symmetrical.)\



There are 16 machines total.

One obvious symmetry would be tape direction (swapping forwards and
backwards)

Another possible symmetry would be data polarity (swap 0 and 1 on the
tape for both input and output). Note that machine 2 of your list is
self symmetric by this measure), and machine 4 is polarity symmetric to
the same machine it is direction symmetric to.

Yes, I miscalculated the number.
When someone says "it's intuitively obvious that" rather than "it is"
then those are what are known as "weasel words". It means "I haven't
proven this rigorously".

But it's obvious that we can't write U(T) - the machine which accepts
a an input in Turing's format, with just one state.
What about two states? Again, presumably we can enumerate, run them on
a input in U(T) format, and show that all the machines get into
a state which is simple on the input. But I don't know how to prove
these things. And of course we can write a machine which is not U(T)
but is in U, that is, we can feed it an input that makes it emulate
U(T).
That sounds like a fairly trivial adjustment to the theory. Why
bother with U(T) when we can convert any machine into U to U(T) ?
Why not just say U?
Well it turns out that when we go to three states, there is a
machine with 2 states and 3 symbols, that is in U, but only if the
tape has an infinite, non-repeating pattern. So it's kind of
in U and not, depending on how we define the requirements for
the conversion header.
http://en.wikipedia.org/wiki/Wolfram's_2-state_3-symbol_Turing_machine

I understand that if there's a 2 state, 3 symbol machine, there must
be a 3-state, 2 symbol machine, because you can swap states
for symbols.
But understanding Alex Smith's proof is way above my level.