# strange warning

Discussion in 'C Programming' started by Bill Cunningham, May 10, 2014.

1. ### Joe PfeifferGuest

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.

Joe Pfeiffer, May 16, 2014

2. ### Ben BacarisseGuest

You do know that I know this stuff, yes?
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?
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.
Ah, you mean that U(2) is a universal TM that expect differently ordered
input. You made very heavy going of saying that.
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.
So what? There is a staggering simple proof of this fact, if you really
want to prove it, but why would you?
See Rice's theorem -- a much better way to get to the fact that the set
of universal TMs is not TM-decidable.
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

Ben Bacarisse, May 16, 2014

3. ### Joe PfeifferGuest

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...

Joe Pfeiffer, May 16, 2014
4. ### Malcolm McLeanGuest

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".

Malcolm McLean, May 16, 2014
5. ### Keith ThompsonGuest

Perhaps they're McLean-identical.

Keith Thompson, May 16, 2014
6. ### Ben BacarisseGuest

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).
At least you were on hand to clear up any confusion.
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?

Ben Bacarisse, May 16, 2014
7. ### Malcolm McLeanGuest

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.

Malcolm McLean, May 16, 2014
8. ### Ben BacarisseGuest

(the snipping may have left it less than obvious that my post was
entirely sarcastic, so it bears saying so here)
I note the "maybe" -- what a delightful detail that is.
Really? What are they?
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).

Ben Bacarisse, May 17, 2014
9. ### Malcolm McLeanGuest

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.
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.

Malcolm McLean, May 17, 2014
10. ### Ben BacarisseGuest

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>

Ben Bacarisse, May 17, 2014
11. ### Malcolm McLeanGuest

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, May 17, 2014
12. ### Malcolm McLeanGuest

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, May 17, 2014
13. ### Malcolm McLeanGuest

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
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.

Malcolm McLean, May 18, 2014