# strange warning

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

1. ### David BrownGuest

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

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
assembly?
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

2. ### Malcolm McLeanGuest

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

Malcolm McLean, May 16, 2014

3. ### Martin ShobeGuest

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. ### Martin ShobeGuest

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. ### David BrownGuest

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

David Brown, May 16, 2014
6. ### David BrownGuest

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. ### James KuyperGuest

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. ### Malcolm McLeanGuest

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. ### James KuyperGuest

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.

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. ### Ben BacarisseGuest

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

Ben Bacarisse, May 16, 2014
11. ### Ben BacarisseGuest

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. ### Ben BacarisseGuest

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?

<snip>

Ben Bacarisse, May 16, 2014
13. ### David BrownGuest

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. ### David BrownGuest

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.
I'm not sure about a "wetware" C compiler...

David Brown, May 16, 2014
15. ### Malcolm McLeanGuest

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.

Malcolm McLean, May 16, 2014
16. ### Ben BacarisseGuest

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

| 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. ### Martin ShobeGuest

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. ### James KuyperGuest

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. ### James KuyperGuest

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. ### Malcolm McLeanGuest

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