strange warning

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

  1. Not really.
    A universal Turing machine can calculate any computable function, given
    enough memory space. That;s not obvious, it's not something I could
    personally have derived from first principles.
    So any Turing machine can emulate any other. That's not entirely
    obvious either, although most people could probably see that it
    follows from theorem one.
    A computer plus a programming language is a Turing machine. Again,
    that's not completely obvious, and it depends how we're using
    the term "programming language". The core members of the set of
    programming languages do turn the computer into a Turing machine,
    but there are marginal cases that don't. There are plenty of
    electronic processing devices that don't ship with programming
    languages, though a programming language might have been used at
    some stage of their manufacture. They're not core members of the
    set "computer", but they are often called "computers", so they
    are marginal members.
    So it follows that any two programming languages are equivalent.
    That's a theorem, it's not a conclusion that relies on observations
    of the external world. We know it must be correct, at least in
    so far as we can trust the internal processes of human reason.
     
    Malcolm McLean, May 15, 2014
    1. Advertisements

  2. Bill Cunningham

    David Brown Guest

    You can derive it from the definition of "computable function" -
    "something that can be calculated by a Turing machine" is one way to
    define "computable function".

    The Church-Turing thesis says that the set of computable functions using
    Turing machines, Universal Register Machines, lambda-calculus, etc., are
    all the same.
    There is basically only one "Turing machine" design. There are a few
    minor variations, but it is obvious that the functions they can compute
    are the same, and it's not hard to prove if you have the mathematical
    background.

    Note that the Church-Turing thesis is a /thesis/, or /conjecture/ -
    meaning it has not been proven, but is generally assumed to be true. To
    be a theorem, it would have to be proven. Of course, it can be proven
    in particular cases (such as proving the equivalence of URMs and Turing
    machines).
    No. A Turing machine has a specifically defined structure, and is
    programmed with a state table. Other computers are not Turing machines.
    (Of course, it would be possible to implement different programming
    languages on Turing machines, but that would a somewhat odd exercise.)
    Again, your terminology is wrong.

    Most general purpose programming languages on most computers are
    approximately Turing complete (i.e., they would be Turing complete given
    enough time and memory). A simple way to view this is that if you can
    implement a Turing machine simulator in the language, then the language
    is Turing complete. Of course, being Turing complete does not imply
    that it is practical to write any sort of function in the language.
    There are lots of useful programmable devices that are not Turing
    complete, and there are lots of programming languages that are not
    Turing complete while still being useful. You would not call these
    "computers".

    There are lots of embedded systems that /are/ approximately Turing
    complete - yet people do not call them "computers" either.
    It follows from the /real/ theory and definitions of computability and
    languages that your statement is incorrect - even when using
    "equivalent" in the very limited sense of being able to compute the same
    functions. All approximately Turing complete programming languages are,
    approximately, able to compute the same functions - assuming the Church
    Turing thesis holds.
    A theorem is a statement that has been proved from a set of accepted
    axioms by a logically valid deduction process. Church-Turing is a
    thesis, not a theorem - it /is/ a conclusion based on observation. We
    currently have no logic system that allows a formal definition of "all
    computation processes" - therefore, we cannot prove a conjecture that
    applies to it. But certainly the Church-Turing thesis has held for all
    the computation processes tried so far.


    I used to have a Turing machine myself, but I can't say I used it much
    (simulations were always easier). I gave it to my computation tutor at
    the end of my degree, as he had always believed them to be purely
    theoretical devices.


    I would recommend you take a wander around Wikipedia. The articles
    covering things like Turing machines, the definition of "theorem", etc.,
    are all pretty good, and would clear up your confusion.
     
    David Brown, May 15, 2014
    1. Advertisements

  3. Bill Cunningham

    Martin Shobe Guest

    Interesting, two squares are identical if you ignore everything that
    differentiates between them. Actually, you've ignored enough differences
    that all parallelograms are identical. Personally, I consider this an
    abuse of the word "identical".
    So you think you've found a counter-example to the Church-Turing thesis?
    And that counter-example is the use of natural language?

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

    Joe Pfeiffer Guest

    One small quibble about your excellent description: while you're right
    about Turing Machines, there have been several very different models of
    computation -- Church's lambda calculus is another well-known one. That
    a TM and the lambda calculus were equivalent was far from obvious (but
    was in fact proven long ago). It was the recognition that several very
    different computational models were equivalent that led to the
    Church-Turing thesis.
     
    Joe Pfeiffer, May 16, 2014
  5. [...]

    This is getting off-topic, but I don't think so. If I understand
    Malcolm's use of the words correctly, neither translation, rotation, nor
    scaling can transform a square into a non-square parallelogram. (I
    presume translation refers to linear motion that doesn't change the
    shape, rotation refers to non-linear motion that doesn't change the
    shape, and scaling refers to a uniform change in size that might change
    a 2-by-2 square to a 3-by-3 square.)
     
    Keith Thompson, May 16, 2014
  6. O-level computer science class. The teacher held up a calculator, my
    calculator as a matter of fact, which is why I remember the lesson.
    "Is this a computer?". "No," said someone, "it doesn't have a memory".
    It had a "mem" button, so he pressed it and showed it had a memory.
    "No," he said, "it doesn't have a backing store. So sorry, McLean,
    but not a computer". And he handed it back to me.

    A computer has state, an internal memory of N bits, giving it 2^N
    states, and it's got a backing store, usually a literal "tape head"
    which is indeed moved up or down a position depending on the state
    of the memory. So it's a Turing machine.

    But it's not a universal Turing machine, not yet. In order to do
    that, we've got to be able to adjust the backing store to put
    it into any internal state we want, or at least a rich enough
    subset of internal states to allow it to compute any function.
    So it needs a programming language. A computer in a random
    internal state might not be able to be used as a universal
    Turing machine, and in fact that frequently happens - a crashed
    computer is in a state from which the rich set of internal
    states are not accessible, regardless of what input we give it.
    All the computers are Turing machines, they all have 2^N possible internal
    states and a backing store. So they can all compute exactly the same
    functions. So in the literal, narrow, mathematical sense, all programming
    languages are equivalent. it's inherently impossible to write a program
    in one language which cannot be written in another.But what if we say the registers are the "internal state" of the computer,
    and the main memory the "backing store". Now we've got a near Turing
    machine, and usually it's better to think that way. So, as well as
    having the fundamental, literal, mathematical equivalence, all non-
    perverse (not designed to expose the fact that the main memory is
    bounded), languages are going to have a another level of deep similarity.

    And there's far more similarity, because again few people who design
    computers or computer languages are perverse. Virtually all languages
    are going to take advantage of the fact the main memory is not a
    tape, but allows random access, for example. Yes, you could write a
    perverse language that didn't, and call it something like "lisp" (to
    indicate that it's a sort of sub-language). But very few people
    use or write languages like that.
    Possibly. However I've used "theorem" in an acceptably accurate sense
    for general discussion. I know that there's a lot of philosophical
    work on the nature of mathematical proof and the relationship between
    maths and formal logic which I don't understand. But I don't think
    anyone except maybe Ben understands it either, and I wasn't trying to
    go there.
     
    Malcolm McLean, May 16, 2014
  7. Bill Cunningham

    Stefan Ram Guest

    That was: what he said.

    »01.03.03
    computer

    A functional unit that can perform substantial
    computations, including numerous arithmetic operations
    and logic operations without human intervention.«

    That was: ISO/IEC 2382-1.

    »2. Normative references« (...) »ISO/IEC 2382-1«

    And that was: N1570 2p4
     
    Stefan Ram, May 16, 2014
  8. Bill Cunningham

    Joe Pfeiffer Guest

    You're using words with precise technical meanings in a context where
    a reader would expect you to be using them with those meanings, but
    meaning some sort of vague English phrase you appear to be inventing on
    the spot instead. It makes conversation impossible.
     
    Joe Pfeiffer, May 16, 2014
  9. Bill Cunningham

    Joe Pfeiffer Guest

    The thing is, that doesn't make it (contrary to his assertion) a Turing
    Machine. It does end up being provable that a reasonable model of a
    computer is computationally equivalent to a Turing Machine -- but that's
    a different claim.
     
    Joe Pfeiffer, May 16, 2014
  10. I don't know a theorem with that name. Do you have a reference?
    I don't know of any such theorem.
    What about languages that are not Turing complete?

    I think you may be confusing some version of the Church-Turing thesis
    (which is not a theorem) with some famous results about the equivalence
    of large classes of programming notations (which are theorems).
    No, I would not object in that way.
    I would object that there is no such theorem. Has the word "theorem"
    got some non-standard meaning for you?
    I don't have a comment to make, I just think a pause is called for
    here...
    Hmm... no, you seem to understand the word as everyone else does.
    Yes, that was my point. Your statement becomes true only when what you
    call the marginal ones are excluded. Ditch the programming languages
    that are not Turing complete, and ditch the languages (and the computing
    devices) that are not Turing equivalent and, yes, you get a set that
    are, well, equivalent by the defining characteristic of the set you've
    made.
    Oh, I have great appreciation for what you've said. In fact you've made
    my day!
     
    Ben Bacarisse, May 16, 2014
  11. Bill Cunningham

    Stefan Ram Guest

    I can't know what the preceding poster had in mind, but the
    English language dictates that an equivalence should be a
    relation, while a theorem is an assertion and the name of a
    theorem should be a noun phrase that designates an assertion
    - not a relation.
    Sounds like a /definition/, not a theorem. »Two devices are
    called "equivalent", when one can emulate the other.«

    However, since there is no »unlimited memory« in this world,
    there are no computing devices in this world (when the
    definition of computing device includes »unlimited memory«).
    This seems to be a non-standard usage of »computation device«,
    since I can see what I'd call »computing devices« in this world.
    I heard this several times from some persons that they
    believe that programming languages must be Turing complete
    or LOOP equivalent, while there is no real fundament for
    this definition - except of course, that anyone is free to
    define concepts as he pleases.

    But let's have a look at ISO/IEC 2382-1:1993, Information
    technology -- Vocabulary -- Part 1: Fundamental terms,
    again, which also is a normative reference for C (N1570)!

    »01.05.10
    programming language
    An artificial language for expressing programs.«

    No reference to Turing completeness or LOOP equivalency!

    »01.05.01
    program

    A syntactic unit that conforms to the rules of a
    particular programming language and that is composed of
    declarations and statements or instructions needed to
    solve a certain function, task, or problem.«
     
    Stefan Ram, May 16, 2014
  12. Not really. Those equivalences are all theorems. The Church-Turing
    thesis is not a theorem -- it's, well, a thesis, that says that all of
    these models of computation capture the intuitive notion of an
    "effective procedure" (the usual translation of the term used by Hilbert
    when he proposed the "Entscheidungsproblem"). As such it can't ever be
    proved because it about an undefined object.

    There are (and were at the crucial time -- the 1930s) other models of
    computation. Some are not Turing-complete (as it is now called) and
    some are complete but not Turing-equivalent (computing with access to
    random bits for example, or to unbounded data). It took some time for
    it to be clear that the Church-Turing thesis is right -- that what we
    consider to be an effective procedure is indeed captured by those models
    that are Turing-equivalent, and not by any others

    One reason it took so much time, and exercised so many great minds, is
    that all Turing-complete models all have the fatal flaw published by
    Turing in his 1936 paper about the Entscheidungsproblem -- that they
    can't decide halting. I prefer to re-phrase that in terms of Rice's
    theorem because it makes that problem so much more dramatic: no
    non-trivial property of the behaviour of programs can be decided.

    Again, not really. I know what you mean, but I think the details
    matter. We know for sure that "all computation processes" are not the
    same because we have loads of counter-examples. We can make them same,
    as Malcolm seeks to, simply by fiat (if it's not Turing-equivalent it's
    not a "computation process"), but that's not a theorem anyone will
    publish.

    Another way to look at it that the Church-Turing thesis describes a
    sweet spot between impractical theoretical models (a TM with a halting
    oracle for example), and inadequate practical systems (like the finite
    computers we actually have). They (TM-equivalent machines) can never be
    made real, but they capture some essential notion of what could be done,
    were resources to be no object.
    Am I missing a joke here?
     
    Ben Bacarisse, May 16, 2014
  13. No. It's a detail, and I know you don't care for details, but a Turing
    machine computes one, and only one, partial function.
    Since it's not true, most people should not see that.
    No. You are mixing categories and then over-generalising. This version
    is true:

    A program is a Turing machine

    provided the language used is "conventional", but to move to all
    programs expressible in a particular language you need an infinity of
    TMs (yes, details again).

    Adding in a computer (presumably you mean a real one, otherwise the
    programming language would do on its own) only makes it less true. You
    end up with, at best, a finite approximation to the set of TMs.

    There are other problems with the remark, but they are subsumed into the
    idea of the language being "conventional". For example, if the computer
    has genuinely random bits (and/or the programming language has such a
    notion) then the equivalence fails.
    That's using the term Turing machine in your own private sense.
    Provided you've excluded the ones that are not. You call them marginal,
    but the people who are actively researching them probably call them
    useful and interesting.
    It's a tautology. Once you eliminate the cases that fail it becomes
    true. No one has (to my knowledge) given that tautology a name, nor has
    anyone published it as a fundamental theorem of computer science.
     
    Ben Bacarisse, May 16, 2014
  14. Yes, far from obvious it may have been, but since it was proved in the
    paper that introduced Turing machines to the world, everyone knew it
    from the get go.
     
    Ben Bacarisse, May 16, 2014
  15. That makes them "equivalent" to sub-Turing-computable models like finite
    state machines.
    But not some TM-computable ones (though the can compute arbitrarily
    close approximations to all TM-computable functions).
    Programming languages can express functions that can't be computed on
    finite hardware.

    <snip>
     
    Ben Bacarisse, May 16, 2014
  16. Bill Cunningham

    Joe Pfeiffer Guest

    I wasn't aware of that -- thank you!
     
    Joe Pfeiffer, May 16, 2014
  17. Bill Cunningham

    Joe Pfeiffer Guest

    I think he's using the computer's entire memory as the state, and
    assuming an infinite backing store. Given those assumptions, the
    computer is Turing-equivalent.
     
    Joe Pfeiffer, May 16, 2014
  18. You've got it.
     
    Malcolm McLean, May 16, 2014
  19. It's "universal Turing machine".
    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.
    So it needs to start off in a "programming state". This is a state
    from which, by feeding it tape with the right sequence of bits,
    we can get it into any other state.
    Secondly, and I'm not entirely clear about this, the state graph
    has to contain a subgraph which is rich enough to be a universal
    Turing machine, that is

    "It is possible to invent a single machine which can be used to compute
    any computable sequence. If this machine U is supplied with the tape on
    the beginning of which is written the string of quintuples separated
    by semicolons of some computing machine M, then U will compute the same
    sequence as M."

    You can see state graphs published which are indeed universal Turing
    machines. I'm not sure what the criteria are for a machine to
    be U.

    So what's programming language? It's the notation of the series of bits
    we can feed to the machine, which will get it from the programming
    state into any other state.
     
    Malcolm McLean, May 16, 2014
  20. Bill Cunningham

    David Brown Guest

    I think I mentioned lambda calculus briefly, but not in detail (I could
    not cover everything) - I used URMs as an example because we studied
    them when I was at university. But lambda calculus is important from
    both a theoretical and a historical viewpoint.

    And you are right that there are lots of different models of computation
    that are all Turing equivalent, such as quantum computing, dna
    computing, and cellular automata.
     
    David Brown, 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.