I have a funtion f: BOOL ⇒ Bool, sich that f(x,y) is true when x=y and false otherwise. Im trying to exhibit a touring machine and a lambda term. for the second part I know that in boolean logic, x ⇒ y iff ¬x ∨ y and these definitions

true := λx. λy. x

false := λx. λy. y

cond := λb. λx. λy. b x y

I came up with the definition for or ∨=λx.λy.(if x then true else y)=λx.λy.cond x true y=λx.λy.x true y., but im unsure how to construct the implication. I know that if x is true, then x→y is equal to y; whereas if x is false, then x→y is always true. For touring machine, I have no idea where to start. any advise?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.