0
$\begingroup$

Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me. But is it correct when we say that a Turing Machine is a WFF ?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes and no. Turing machines aren't WFF, but can be encoded as a WFF. The definition of TMs uses sets and functions (which aren't symbols in the alphabet), but its possible to create a one-to-one encoding from TMs to WFF. Usually, given a TM $M$, we refer to its encoding as $\langle M\rangle$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.