Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!netnews.upenn.edu!msuinfo!rang
From: rang@cs.wisc.edu (Anton Rang)
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Message-ID: <RANG.91Feb11164748@nexus.cs.wisc.edu>
Date: 11 Feb 91 21:47:48 GMT
References: <1991Feb7.150537.9257@spool.cs.wisc.edu>
	<RANG.91Feb10140506@nexus.cs.wisc.edu> <319@smds.UUCP>
Sender: news@msuinfo.cl.msu.edu
Organization: UW-Madison CS department
Lines: 56
In-Reply-To: rh@smds.UUCP's message of 11 Feb 91 09:55:01 GMT

In article <319@smds.UUCP> rh@smds.UUCP (Richard Harter) writes:
>[I wrote:]
>>   I claim that, given any Turing machine, I can write a Pascal or C
>> program which will perform exactly the computation that machine would
>> perform on a given input.  (You can't do it in FORTRAN, because you
>> don't have dynamic memory allocation.)
>
>Sorry, Dan is right on this one, and it is actually important to understand
>that he is right and why he is right.  Turing machines do not exist in
>the real world -- they require as part of the definition infinite memory.

  Turing machines don't exist in the real world.  However, it is
reasonable (IMHO) to assume that because many computer languages do
not place restrictions on the operations used (such as "allocate
memory" or "perform a procedure call"), the *language* assumes an
infinite model for such resources as stack and dynamic memory.

  If I write a procedure in Pascal:

	procedure forever;
	begin
	  forever
	end;

and call it, the *language* semantics (which can be formally defined)
probably say that this will never terminate.  (It is possible to
define the semantics in such a way that a procedure call can lead to
an error at random, of course.)  On a real machine, this may run
forever, or it may abort with a stack overflow error.  The
*implementation* of the language places restrictions on what legal
programs can be run.

>The statement "real languages are not equivalent to Turing machines"
>isn't exact (it mixes languages and machines which are two different
>concepts) but the intent is clear.

  It's not really clear to me.  "Real languages" and "real machines"
are radically different, in my mind (with the exception of, e.g., an
assembly language which defines a fixed data store size etc.).

>Programs which execute on real computers are not equivalent to Turing
>machine programs in general.

  Yes, but "programs which execute on real computers" is a strictly
smaller set than "programs which are expressible in real programming
languages," I believe.

>The distinction is important.  There are many statements that are true
>for Turing machines that are not true for real computers.  Etc.

  Very true (this is why the "halting problem" is defined for Turing
machines, and is meaningless for an implementation on a FSM).  There
are also many statements that are true for programming languages which
may not be true of a particular implementation.

	Anton
   
+---------------------------+------------------+-------------+
| Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison |
+---------------------------+------------------+-------------+