Turing Compliant?
Stephan Houben
stephan at pcrm.win.tue.nl
Thu Sep 2 04:05:38 EDT 1999
David Oppenheimer <davidopp at megsinet.net> writes:
> What the heck does Turing Compliant mean? I've heard discussion that
> Python is not Turing Compliant. Is this true and why would this be an
> important consideration for someone who is programming in Python?
I'm sorry. I'm probably to blame for this.
Someone asked a question whether Python was suited for his goals, without ever
mentioning what his goals where. So I asked him what his goals where, and
-as a joke- if Turing Completeness was perhaps required.
Every programming language is Turing Complete. This is a bit like when
somebody asks which car he should buy, and I ask him if it is supposed to be
able to drive. So it was a lame joke, and it confused people.
So to make mends for all this, I will now give a constructive proof that
Python is, indeed, Turing Complete. I will do this by including the
following Python program, which is an evaluator for the Lambda calculus.
(The Lambda calculus is Turing complete, almost by definition.)
Note the syntax: angles are required around applications, like in
(f g), but forbidden diectly around lambda abstractions.
Lambda abstractions are written as:
\x.expr
The interpreter reads one line at a time. An empty line exits the interpreter.
I actually tried to do some sane error recovery.
However, the implementation is NOT efficient.
But who cares. It terminates.
Greetings,
Stephan
# Lambda calculus interpreter in Python.
# This is a constructive proof that Python is Turing-complete.
# Written by Stephan Houben
import string
import types
class ParseError(Exception):
pass
def parse(str):
# crude hack to have "(", ")", "." and "\\" always stand out
str = string.replace(str, "(", " ( ")
str = string.replace(str, ")", " ) ")
str = string.replace(str, ".", " . ")
str = string.replace(str, "\\", " \\ ")
# split in tokens
tokens = string.split(str)
expr, i = parse_expr(tokens, 0)
if i < len(tokens):
raise ParseError, "Superfluous input found"
else:
return expr
def get_token(tokens, i):
if i >= len(tokens):
raise ParseError, "More input expected"
else:
return tokens[i], i+1
def check_token(tokens, i, token):
token2, i = get_token(tokens, i)
if token != token2:
raise ParseError, "Token %s expected instead of %s" % (token, token2)
else:
return i
def parse_expr(tokens, i):
token, i = get_token(tokens, i)
if token == "(":
expr1, i = parse_expr(tokens, i)
expr2, i = parse_expr(tokens, i)
i = check_token(tokens, i, ")")
return (expr1, expr2), i
elif token == "\\":
var, i = get_token(tokens, i)
check_var(var)
i = check_token(tokens, i, ".")
expr, i = parse_expr(tokens, i)
return ("\\", var, expr), i
else:
check_var(token)
return token, i
def check_var(token):
if token in ("//", "(", ")", "."):
raise ParseError, "Variable expected instead of %s" % token
def is_var(expr):
return type(expr) == types.StringType
def is_application(expr):
return type(expr) == types.TupleType and len(expr) == 2
def is_lambda(expr):
return type(expr) == types.TupleType and len(expr) == 3
def substitute(expr, var, subst):
if is_var(expr):
if expr == var:
return subst
else:
return expr
elif is_application(expr):
return (substitute(expr[0], var, subst),
substitute(expr[1], var, subst))
else:
lambda_var = expr[1]
if lambda_var == var:
return expr
else:
return ("\\", lambda_var, substitute(expr[2], var, subst))
def evaluate(expr):
while is_application(expr):
f, g = expr
f = evaluate(f)
if is_lambda(f):
lambda_var = f[1]
lambda_body = f[2]
expr = substitute(lambda_body, lambda_var, g)
else:
break
return expr
def prettyprint(expr):
if is_var(expr):
print expr,
elif is_application(expr):
print "(",
prettyprint(expr[0])
prettyprint(expr[1])
print ")",
else:
print "\\",
prettyprint(expr[1])
print ".",
prettyprint(expr[2])
def main():
while 1:
line = raw_input("> ")
if line:
try:
prettyprint(evaluate(parse(line)))
print
except ParseError, msg:
print "Error: %s\n" % msg
else:
break
main()
More information about the Python-list
mailing list