This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: turing completeness


klaus@debian said:
> I recently heard that scheme is turing complete, but saw no
> explanation. Anyone here may explain what that means?

This has nothing to do with guile, of course.

ObGuile:  I'm really impressed by the work going into GNOME, and especially 
the GIMP (although I think the gimp is SIOD based, currently).  The gimp could 
easily become a killer free app, it's amazingly cool.  And Gtk, the toolkit 
that they're using looks very nice.

Something that can compute all functions that a universal Turing machine can.  
Equivalently, a language which can express a program that can compute any 
function that any specific Turing machine can.

>  What languages are not turing-complete? 

A language without control structures, for example.  Where the only legal 
statements are

<var> := <expr>

where <expr> is some expression including, say, variables, constants and the 
four binary operators (+, -, *, /).

A less uninteresting one would be one which included finite for loops.  So 
you'd allow

for <var> = <low> to <high>
   <statements which don't modify <var>>
endfor

That still disallows the computation of interesting functions.  And partial 
functions, of course (where the value is undefined for some input parameters).