1
$\begingroup$

During my study of Finite Model Theory I found that usually purely relational structure say $\mathcal{M} = \langle A, R_1,\ldots,R_k \rangle$ are encoded as

$0^n1$#$\operatorname{enc}(R_1)$#$\operatorname{enc}(R_2)$#$\ldots$#$\operatorname{enc}(R_k)$

where n is the size of universe A and each $\operatorname{enc}(R_i)$ is a binary string of length $n^{m_i}$ for $1 \leq i \leq k$ and $m_i$ being arity of each relation $R_i$. Any position j of such binary string is $1$ iff corresponding $m_i$-tuple (from set of lexicographically ordered $A^{m_i}$) belongs to relation set $R^{m_i}$ and $0$ otherwise.

My concern is how we encode any first-order formula $\phi$ using strings of symbols recognised by Turing machine.

  • 0
    The same way we encode them on a computer as a string of bits.2011-09-01

1 Answers 1

1

I assume your Turing Machine can only read $0$ and $1$. Here is one (very inefficient) way of encoded first order formulas in a finite language:

Assuming you are working in a fixed finite language in first order logic. Including all the logical symbols (equality, parenthesis, negation, etc), there is a finite number of symbols. Let $n$ denote the number of these symbols. Assign each of these symbols a number. Let $n + k$, denote variable $x_k$.

Let each symbol be represented by that many 0's. Let 1 serve as a separator. For example if "$=$" has number 3 and the language has only 6 symbol not including variables, then "$x_1 = x_2$" can be encoded as $00000001000100000000$.

Of course there are much better ways of doing this. One way is if you permit more basic symbols in your Turing Machine language (to begin with).