strange warning

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

  1. Bill Cunningham

    David Brown Guest

    No. First off, a Turing machine is a computer - a computer is not a
    Turing machine. Here are some pictures of Turing machines, since you
    apparently don't like to look at Wikipedia for a formal definition:


    Secondly, there is no precise or concrete definition of a "computer",
    except perhaps "something that computes". ("Computable functions" have
    a precise definition.) Before electronic computers, a "computer" was a
    person who did a lot of calculations. So your teacher got it wrong -
    your calculator /is/ a computer, even though we generally use the term
    for more general-purpose computers. Backing store certainly doesn't
    come into it.
    Your calculator is not a Turing machine. It is not approximately Turing
    equivalent, because it has limitations (besides memory) that prevent it
    from executing different algorithms. (A calculator with a user is
    Turing equivalent, however.)

    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.
    How many mistakes can be made in one sentence, I wonder?

    As I said above, computers are not Turing machines, any more than birds
    are ducks.

    There is absolutely no restriction to having 2^n possible states in a
    computer - while base 2 representations are the most practical for
    electronic computers, they are not essential. There have been computers
    made using base 3 and base 5 elements, or whose states are enumerated as

    And as noted above, a backing store is not needed.
    All Turing equivalent systems of computer and programming language can
    compute the same functions (bare memory limitations).
    No, all Turing complete or Turing equivalent programming languages (on
    suitable targets) are equivalent in the single aspect of being able to
    compute the same functions. They are not equivalent in "/the/
    mathematical sense", because there is no such single thing - and they
    will often be very different in real mathematical aspects, such as time
    and space efficiency.
    That is an alternative statement of the Church-Turing conjecture.
    First, there are lots of programming languages that are not perverse,
    and are still not Turing complete. It is extremely common for
    domain-specific languages.

    Secondly, in many cases the Turing equivalence of programming languages
    is /very/ deep. Yes, Prolog and APL /can/ compute the same functions -
    but that is an irrelevant fact in practical usage, and the languages are
    used for wildly different kinds of problems.
    I take it you have never met a computer or computer language designer.
    Most of them are more than a little weird :)
    You have such a narrow view of programming languages. Have you ever
    really looked at any programming languages other than C and perhaps
    No you haven't - you have used it in an incorrect sense, and argued
    repeatedly that you were being accurate despite being corrected.
    Then accept it when people are telling you the correct terms to use.
    There is nothing wrong with ignorance - even the oldies here don't know
    everything. But there is something very wrong with wilful and stubborn
    ignorance, and a refusal to accept that you have been corrected,
    especially when it is all so easy to check.
    David Brown, May 16, 2014
    1. Advertisements

  2. The universal Turing machine has a state graph which means that, when fed
    the quintuple state graph of an arbitrary Turing machine, it emulates or
    becomes that machine.
    So if our state graph for out 2^(2^32) + 32 * 2^32 typical architecture
    physical Turing machine contains a subgraph which is U, we can set it
    to that sate, it becomes U, and it will process any function in the input
    format devised by Turing himself.
    What if it doesn't have a substate which is U? Well there was nothing
    fundamental about Turing's format. For example, there are 5! possible
    arrangements of the quintuples. So let's call Turing's U (T), and the
    5! other Turing machines U(x), where x is a number from 1 to 5! and
    U(1) = U(T).
    We can very easily process an input, in Turing's format, by specifying
    U(T) in the format for U(x). So the input needs a header.
    But generally for a commuter, the state graph is so massive, that
    there are plenty of sub-graphs which are U(T). There are also plenty
    of subgraphs which are the machines we actually want. We seldom
    have to go through state U.
    Fair enough. basically the computer has vast but finite number of internal
    states. We disconnect the keyboard mouse, and all but one of the disk drives.
    So all it can do is go into one of the 3^(3^32) internal states (assuming 3 state
    bits), read a bit from the disk in the current position. That state and the bit
    read then completely define the next state it will enter. It moves the head,
    writes a bit, and the process repeats.
    It's a physical realisation of Turing's machine. That's what it is, not theoretically,
    but practically and exactly. It's just that the state graph is extremely large
    and complex. You want that, because it's easier in reality to select a useful
    sub-graph, that to to to sub-graph U(t) and process everything in Turing's
    bit format.
    Yes it is. The backing store is essential. That's the entire crux of the
    Malcolm McLean, May 16, 2014
    1. Advertisements

  3. Bill Cunningham

    Martin Shobe Guest

    There is such a thing as a universal Turing machine. It's a Turing
    machine whose input is an encoding consists of an identifier for a
    Turing machine and the input to be fed to it. It leaves on the tape
    exactly what the Turing machine identified input would have left when
    fed the specified input.

    Martin Shobe
    Martin Shobe, May 16, 2014
  4. Bill Cunningham

    Martin Shobe Guest

    I misunderstood then, I thought he meant scaling in way that included
    transformations such as mapping (x, y) to (2x, y).

    Martin Shobe
    Martin Shobe, May 16, 2014
  5. Bill Cunningham

    David Brown Guest

    The equivalences of Turing machines, URMs, and lambda calculus are all
    theorems - it's the "etc." that makes it a thesis. As you say, this is
    because the "etc." is not defined and thus cannot be proven.
    Yes, there are certainly computational processes that are not Turing
    complete. An example close to our hearts is the C pre-processor
    language - it can compute some things, but not everything.
    I certainly wasn't being very serious, but I really did have a Turing
    machine. It was a model I had acquired somewhere, with a paper tape, a
    "read/write head" (actually just a slot in which the tape sat, where you
    could view or change the current element but not the neighbours, to
    discourage cheating), and a pad of paper for writing the program. It
    was all made out of paper and cardboard. The tape wasn't very long - by
    the time you had seen how to do "1 + 2", you would never bother using it
    for anything larger.

    I've been trying to find a balance in these posts between being accurate
    and being understandable - it's good that there is someone checking my
    David Brown, May 16, 2014
  6. Bill Cunningham

    David Brown Guest

    Fair enough. I have been using the term "Turing machine" as one that
    can be programmed by using a different state table. If you consider the
    state table to be a fixed part of a particular Turing machine, then each
    Turing machine only computes one fixed function. A Universal Turing
    machine is then a Turing machine whose single fixed function is to run a
    simulation of a tape input specified Turing machine on the rest of the
    tape. The fact that such Universal Turing machines are possible means
    that we can simplify things a bit and work with programmable Turing
    machines rather than "making" new ones all the time. But maybe there
    was place for more precision in my posts in this regard.
    David Brown, May 16, 2014
  7. Bill Cunningham

    James Kuyper Guest

    I think that what Malcolm means is that all squares have something in
    common, namely "squareness". What he's actually saying is that they are
    equivalent, which, according to proper usage of English, would mean that
    they had everything is common, not just squareness. That is manifestly
    false - but I'm pretty sure it's not what he actually means.
    The transformations he lists are ones that preserve squareness. The
    transformation you mention does not.
    James Kuyper, May 16, 2014
  8. Exactly. Most computers will have a subgraph of states that represent
    the Turing machine we want to do the calculation. So we drive it into
    that internal state (programming), and then feed it the input (running).
    But occasionally that might not be possible, but if it has a sub-graph
    that is U(T), Turing's universal machine, then we can drive it to U(T),
    feed it the state graph we want, then feed it the input. If it doesn't
    have an internal sub-graph which is U(T), we can drive it to a state which
    is U(T) equivalent, eg U(2) (U(T) with two numbers transposed) . We then
    specify U(T) in U(2) format, and we're in business.

    I think that's it. I think we only ever need 3 levels of emulation, but I'm
    open to correction on that.
    Malcolm McLean, May 16, 2014
  9. Bill Cunningham

    James Kuyper Guest

    On 05/16/2014 07:04 AM, David Brown wrote:
    ISO/IEC 2382-1, section 01.03.01 contains a definition for "computer",
    and section 2p4 of the C standard makes that definition normative in the
    context of the C standard. Stefan Ram has already cited that definition,
    which I have to admit, is neither particularly precise or concrete. It
    is, however, applicable, and somewhat more precise than "something that

    Since the word "computer" occurs only once in the entire standard
    (K.1p3), and only as a part of a statement of fact, not as part of the
    specification for any aspect of C, the imprecision of that definition
    isn't particularly important.

    That's good, because ISO/IEC 2832-1's definition explicitly dis-allows
    calling a human a computer. I've always been rather fond of the idea
    that wetware implementations of C are possible, at least in principle.
    James Kuyper, May 16, 2014
  10. 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.
    Ben Bacarisse, May 16, 2014
  11. Of course. Everything Malcolm says is correct. The key is for everyone
    else to work out how he is using words, what assumption are un-stated,
    and to ignore any resulting oddities.
    Ben Bacarisse, May 16, 2014
  12. To what does the "it" refer?

    A universal Turing machine is an example of what I said -- it computes
    one, and only one, partial function.
    Eh? I don't think you know what a TM is or what a UTM is.
    Really? Why are you pontificating about them, then?

    Ben Bacarisse, May 16, 2014
  13. Bill Cunningham

    David Brown Guest

    That can't be right - we might agree that the person who brought up
    Turing is wrong, but it hasn't stopped us arguing.
    David Brown, May 16, 2014
  14. Bill Cunningham

    David Brown Guest

    I was talking about a more general definition of the term "computer"
    than the specific C standards definition, since we are quite a bit away
    from C in this thread. Of course, the C standards definition is still
    I'm not sure about a "wetware" C compiler...
    David Brown, May 16, 2014
  15. If it's U(T) then it takes a quintuple Turing machine in Turing format, and
    emulates it. Obviously there a U(2), which does the same, but with two
    of the columns transposed. And of course there's a infinite number of
    transformations like that we can apply to the data, whilst keeping the
    But I'm not sure how you recognise that a machine is actually in U.
    There are limits to what I know.
    Malcolm McLean, May 16, 2014
  16. I have no idea what this means, but how could it possible be an answer
    to my question? I suspect more private language and notation. U(T)
    looks like a function application, but U(2) probably isn't, so maybe
    not. And, of course, it's up to anyone reading this to guess what on
    earth is meant by "columns". (Yes, I can guess, but none of my guesses
    help to make sense of this.)
    Eh? Are you speaking your own language again? But why do you ask this?
    How does it answer my question?
    My question was supposed to be about the whole message. This is c.l.c
    so there is probably little worry, but what would happen if someone
    learning computability theory read this:

    | It has a set of internal states, and a read head. When it reads a bit,
    | depending on state it writes a bit, move the head up or down, and
    | goes into a new state. But most such machines can't calculate any
    | interesting function.

    Obviously this must be correct, but I am at a loss to know what private
    meanings must be understood for these words, what un-stated assumptions
    must be in play, and what details must have been swept under the carpet
    to make it so. What hope for a beginner?
    Ben Bacarisse, May 16, 2014
  17. Bill Cunningham

    Martin Shobe Guest

    So, you think he was saying, "All squares are squares", in a round-about
    way? I suppose I can't argue with the truth of what he said then, but I
    still find that an abuse of the word "identical".

    Martin Shobe
    Martin Shobe, May 16, 2014
  18. Bill Cunningham

    James Kuyper Guest

    Many years ago, someone posted a message to either this forum, or
    comp.std.c (I can't remember which) claiming that he himself qualified
    as a conforming implementation of C - if you wrote down a C program and
    handed it to him, he would engage in behavior that would would meet the
    requirements of the C standard for a fully conforming implementation.
    I'm don't think anyone ever put that claim to the test, but I don't know
    of any insurmountable difficulties with the idea. For a program of any
    significant size, it would require near-photographic memory and would
    usually run far slower than most software implementations.
    James Kuyper, May 16, 2014
  19. Bill Cunningham

    James Kuyper Guest

    On 05/16/2014 10:59 AM, Martin Shobe wrote:
    More precisely, "All squares are square".
    I'm in full agreement.
    James Kuyper, May 16, 2014
  20. 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. Now let's call that machine U(T), because it's
    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. 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.
    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
    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 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. 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.
    Malcolm McLean, May 16, 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.