λ

λ is Lambda calculus but it has a few changes. it was created by User:Yayimhere

changes

• a program halts when no changes happen to any expression
• theres no simplification. only beta reductions
• encasing a expression in {} will make it loop until the program would halt
• the first line must be empty
• ! will be replaced with user input
• ^ at the end of a function(in brackets) will when evaluated will print itself

turing completeness proof

a version of thue an be translated to λ(this version is a Thupit). the modified version thue applies the replacements from top to bottom(don't tell me this means its not Turing complete i swear if it is, i'll go insane). so say we have the program:

x::=y
z::=y
y::=d
::=
zzd

this is the same as the λ program:

{(λx.(λz.(λy.(zzd)d)y)y)}

here is how it works:

• the first replacement has the structure {(λpattern.(rest of program)(replacement^))}
• the ones between are (outer(λpattern.(inner program))(replacement^))program)
• and the last replacement is (outer(λpattern.(program string))(replacement^))program)
• the ^ must be deleted to not perform the output
• if ! is used in the pattern or replacement its input

so the truth machine(with some redundancy i think) from the thue page:

{((λ*.(λ1.((λ_.((λ0.(*))(0^)))(1^)))1_))!)}