strange warning

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

  1. Bill Cunningham

    Joe Pfeiffer Guest

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

  2. 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
    about this? I wanted to close the technical discussion off, but I was
    curious about why you thought you should post about this stuff.
     
    Ben Bacarisse, May 16, 2014
    1. Advertisements

  3. Bill Cunningham

    Joe Pfeiffer Guest

    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. 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. Perhaps they're McLean-identical.
     
    Keith Thompson, May 16, 2014
  6. 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. 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. (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. 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 :eek:n bit 0: write bit 1: forwards: goto state 1
    in state 1 :eek: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. 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. 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. 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. 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.
     
    Malcolm McLean, May 18, 2014
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.