strange warning

[David Brown]

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.

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:

<https://www.google.com/search?q=turing+machine&source=lnms&tbm=isch>

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.

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.

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.

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.

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

And as noted above, a backing store is not needed.

So they can all compute exactly the same
functions.

All Turing equivalent systems of computer and programming language can
compute the same functions (bare memory limitations).

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

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.

it's inherently impossible to write a program
in one language which cannot be written in another.

That is an alternative statement of the Church-Turing conjecture.

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.

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.

And there's far more similarity, because again few people who design
computers or computer languages are perverse.

I take it you have never met a computer or computer language designer.
Most of them are more than a little weird

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.

You have such a narrow view of programming languages. Have you ever
really looked at any programming languages other than C and perhaps
assembly?

Possibly. However I've used "theorem" in an acceptably accurate sense
for general discussion.

No you haven't - you have used it in an incorrect sense, and argued
repeatedly that you were being accurate despite being corrected.

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.

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.

 

[Malcolm McLean]

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.

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.

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

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.

And as noted above, a backing store is not needed.

Yes it is. The backing store is essential. That's the entire crux of the
system.

 

[Martin Shobe]

On 16/05/14 02:03, Malcolm McLean wrote:
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.

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]

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

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

Martin Shobe

 

[David Brown]

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.

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.

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.

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.

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?

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
accuracy!

 

[David Brown]

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.

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.

 

[James Kuyper]

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

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

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.

 

[Malcolm McLean]

On 16/05/14 13:38, Martin Shobe wrote:

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.

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.

 

[James Kuyper]

On 05/16/2014 07:04 AM, David Brown wrote:
....

Secondly, there is no precise or concrete definition of a "computer",
except perhaps "something that computes". ("Computable functions" have
a precise definition.)

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

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.

 

[Ben Bacarisse]

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

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]

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.

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]

It's "universal Turing machine".

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.

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.

Eh? I don't think you know what a TM is or what a UTM is.

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.

Really? Why are you pontificating about them, then?

<snip>

 

[David Brown]

Arguing the toss about what is or isnt a Turing complete blah blah is
the c.l.c equivalent of Godwin's.

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]

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

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.

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

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.

I'm not sure about a "wetware" C compiler...

 

[Malcolm McLean]

Really? Why are you pontificating about them, then?

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
information.
But I'm not sure how you recognise that a machine is actually in U.
There are limits to what I know.

 

[Ben Bacarisse]

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

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

But I'm not sure how you recognise that a machine is actually in U.

Eh? Are you speaking your own language again? But why do you ask this?
How does it answer my question?

There are limits to what I know.

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?

 

[Martin Shobe]

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

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

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.

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

 

[James Kuyper]

On 16/05/14 14:40, James Kuyper wrote: ....

I'm not sure about a "wetware" C compiler...

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]

On 05/16/2014 10:59 AM, Martin Shobe wrote:
....

So, you think he was saying, "All squares are squares", in a round-about
way?

More precisely, "All squares are square".

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

I'm in full agreement.

 

[Malcolm McLean]

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

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

Eh? Are you speaking your own language again? But why do you ask this?
How does it answer my question?

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.