strange warning

[Malcolm McLean]

Using your analogy, "identical to a square apart from translation,
rotation, and scaling" is not a theorem. "Some particular entity is
identical ..." or "some set of entities are identical ..." might be a
theorem.

You're just misusing the word "theorem", that's all.

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.

 

[David Brown]

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.

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.

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.

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

A computer plus a programming language is a Turing machine.

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

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.

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.

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.

So it follows that any two programming languages are equivalent.

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.

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.

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.

 

[Martin Shobe]

You're making the same mistake as Ben.

Of course Turing equivalence is a "theorem". Just as the theorem that
any two squares are identical part from translation, rotation, and scaling.

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

Ok, but what if we're not talking about the Euclidean plane? What about
Trafalgar square - that's a square, isn't it?

It becomes tautological. If a computer isn't Turing complete, or if it is
capable of determining a non-computable function (e.g. if it can use
natural language), then it's not a "computer". It doesn't mean that
Turing was saying nothing.

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

 

[Joe Pfeiffer]

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

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.

 

[Keith Thompson]

On 5/15/2014 12:52 PM, Malcolm McLean wrote: [...]

Of course Turing equivalence is a "theorem". Just as the theorem that
any two squares are identical part from translation, rotation, and scaling.

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

[...]

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

 

[Malcolm McLean]

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

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.

Of course, being Turing complete does not imply that it is practical
to write any sort of function in the language.



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.

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.

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

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.

 

[Stefan Ram]

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.

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

 

[Joe Pfeiffer]

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.

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]

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

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.

 

[Ben Bacarisse]

The conventional name is Turing equivalence.

I don't know a theorem with that name. Do you have a reference?

This means that any computing
device many emulate any other, given only unlimited memory or storage
space.

I don't know of any such theorem.

It follows from that that, given a few conditions, any computer
language may emulate any other. So all languages have a fundamental
similarity.

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

Now you might object that, if we implement a simple Turing machine with
a pencil, rubber, read head, and infinite paper tape, we can write a
C compiler for it, but we can't possibly provide O(constant) time
access to an array.

No, I would not object in that way.

The fundamental theorem is that all computations
are at root the same thing. The real observation is that most if not
all rational, practical, in-use etc programming languages on real,
existing devices will operate in much the same way. That follows
from the fundamental theorem,

I would object that there is no such theorem. Has the word "theorem"
got some non-standard meaning for you?

but it's not actually imposed by it.
Everyone who implements an array is going to calculate a memory
index then index into it, for example. The array may be broken up,
it may have strides it it, it may have a layer of indirection under
it via a hash table. But it's still at bottom going to work in the
same way.

If you're going to argue, you have to understand natural language.
You speak English fluently, probably as first language, so you
do have an intuitive understanding of language which is good enough
to discuss technical points. Your understanding is not good
enough for you to participate competently in a philosophical debate.

I don't have a comment to make, I just think a pause is called for
here...

You try to nitpick on the word theorem. "Theorem" means, "something
which is known form pure logical deduction, as opposed to know
from observation", in normal usage.

Hmm... no, you seem to understand the word as everyone else does.

It might have a technical
mathematical definition that I an the normal person is unaware
of, and you can point that out. But you have to be careful that
you're not just being a clever dick.
Similarly "programming language" is a class which has core members
and marginal members. The word "all" doesn't necessarily cover
the marginal members of the set, it also excludes some special
case ("All Britons are subjects of the Queen" - well no, not the
Queen herself, it doesn't mean that the claim is in any normal
sense false).

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.

Now I don't believe you don't know I'm talking about Turing
equivalence. But what the main thrust of what I was saying
wasn't a claim about mathematical equivalence. You have to
understand that the mathematical equivalence is there before
you can really appreciate what I am saying, however.

Oh, I have great appreciation for what you've said. In fact you've made
my day!

 

[Stefan Ram]

I don't know a theorem with that name. Do you have a reference?

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.

I don't know of any such theorem.

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.

What about languages that are not Turing complete?

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

 

[Ben Bacarisse]

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.

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.

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.

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.

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.

Am I missing a joke here?

 

[Ben Bacarisse]

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.

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.

That's not entirely
obvious either, although most people could probably see that it
follows from theorem one.

Since it's not true, most people should not see that.

A computer plus a programming language is a Turing machine.

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.

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,

That's using the term Turing machine in your own private sense.

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.

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.

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.

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]

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

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]

All the computers are Turing machines, they all have 2^N possible internal
states and a backing store.

That makes them "equivalent" to sub-Turing-computable models like finite
state machines.

So they can all compute exactly the same
functions.

But not some TM-computable ones (though the can compute arbitrarily
close approximations to all TM-computable functions).

So in the literal, narrow, mathematical sense, all programming
languages are equivalent.

Programming languages can express functions that can't be computed on
finite hardware.

<snip>

 

[Joe Pfeiffer]

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.

I wasn't aware of that -- thank you!

 

[Joe Pfeiffer]

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>

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.

 

[Malcolm McLean]

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.

You've got it.

 

[Malcolm McLean]

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.

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.

 

[David Brown]

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.

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.