Re: a language is a language

Just to clear up some of the confusion I see here ...

Arthur J. O'Dwyer wrote:
On Wed, 13 Dec 2006, Pascal Bourguignon wrote:
"sjdevnull@xxxxxxxxx" <sjdevnull@xxxxxxxxx> writes:

Turing hasn't been refuted, but to most people "programming language"
is different from "thing that's Turing-complete".

You are confusing "computer language" with "language implementation".
The OP asked about languages, IIRC, not about implementations of
those languages.


If you insist that "programming language" includes only truly
Turing-complete constructs, then you're excluding languages like C from
the definition (C allows for implementation-defined limits on all
resources that can be much lower than those of the platform the
implementation is running on).

Only for implementation; a C program can happily be infinite/unbounded
in length and use, provided that a suitably long tape is available.

[...]
(And this has nothing to do with HTML, which falls short of a lot more
than just infinite storage).

Turing Machines don't require infinite storage.
They require unbounded a-priori storage.

Since any working Turing Machine must terminate in a finite number of
step, let's call this number S, it cannot use more than S cases on the
tape, either up or down. So if you start with a finite tape of length
2S+1, you can run any Turing Machine program that terminates in S
steps or less.

Yes; sjdevnull was using the term "Turing machine" a little more
loosely than you are. One common perception of the Turing machine
is as a program that accepts /input/ and produces /output/, a la
a finite state machine. For example, consider the program

function ReverseInput(input as head::rest)
if (head is null)
return
ReverseInput(rest)
print to output (head)
return

Now, any reasonable person would agree that this function is "computable
by a Turing machine", in which case they'd be thinking of the machine
as consuming some kind of "input tape" and producing another tape as
output. In practice, what this means is that the machine has a "scratch
pad" that's as big as its input.

Nope; what this means is that the implementation of your language
above may need finite resources. The language itself has no
limits besides the ones you decide to pose arbitrarily (maybe
because of implementation headaches?).


Since the machine can take any input whatsoever, its scratch pad
needs to be as big as any input whatsoever --- i.e., unbounded.
Again, using the popular and looser terminology, this is often called
"infinite" storage space.

Now, you certainly know all this already, and we know you know it,
and you know we know you know it. So why bother with the semantic
games? Turing machines may not "require infinite storage", but any
implementation of a Turing machine /does/.

Of course, any implementation will have finite requirements, but the
OP never mentioned implementations; the question was with regard to
"languages", not "language implementations".

sjdevnull's point is
perfectly and totally valid.

Only if the question is rephrased as "which of the following
language implementations are true programming languages?".

If the original posters question still stands, then
sjdevnull's point is wrong. The answer sjdevnull offered
was correct for a different question, not this question.



Most modern programming languages are not Turing-complete.

Wrong. Most modern programming languages *are*, in fact, turing-
complete. Most modern programming language implementations are
not.


No physical computer is Turing-complete.

Correct. This has absolutely no relevance to the question of
whether the language itself is turing-complete.



There's also another point that's often forgotten about Turing
Machines, is that they have a _fixed_ program. Like the program of a
processor is fixed in the silicium.

As someone who writes firmware, I find this distinction funny.
Almost anything done in software can be /hardwired/ into hardware,
and almost anything done in hardware can be emulated in software.


(FYI, the English word is "silicon".)



goose,

.

Relevant Pages