P.H.P. and Python (and Tcl/Tk!)

[Dave Mason]

>> The closest thing that arguably is not is sed.

> Someone here claims sed is turing complete (I dno't want to try and
> prove it one way or the other that's for sure):
> http://sed.sourceforge.net/grabbag/scripts/turing.sed

I did say "arguably", and I hesitated about saying even that.  (I also
had a grad student who had written a turing machine in sed (in a
previous life), but I had never had the energy to try to figure it out.)
If I added the restriction: "original sed, before they added the looping
construct" it certainly isn't Turing complete, but that's going back
pretty far.

I was trying to give people some perspective on how little Turing
completeness actually says about a language.  Bottom line is it's hard
to come up with an extant "programming language" that isn't Turing
complete.  XSLT is another example of something that is.  Usually these
days it's a very concious effort to make a language not Turing complete
(so you can guarantee termination of any calculation).

The Wikipedia article at
	http://en.wikipedia.org/wiki/Turing_completeness
suggests cycle-free spreadsheets (ignoring already Turing-complete
extension languages like BASIC) and standards-compliant SQL as well
known examples.  (Note that, depending on the implementation of the
spreadsheet, a cyclic construct could allow you to write a Turing
machine in a spreadsheet.)

../Dave
--
The Toronto Linux Users Group.      Meetings: http://gtalug.org/
TLUG requests: Linux topics, No HTML, wrap text below 80 columns
How to UNSUBSCRIBE: http://gtalug.org/wiki/Mailing_lists