Is DFA (Deterministic Finite Automata) a kind of predicate?

Question

When I read a book on computation theory, I found a interesting thing: A Language L was defined by a DFA(Deterministic Finite Automata) like this,

L = {$\omega$ | the last input of $\omega$ causes the DFA to halt in one of the accepting states}

It is quite similar to the form:

S = {x | P(x)}

Using the DFA can decide whether a Language is accepted or not. This makes me to think that DFA functions like predicate here.

If my observation is correct, then are there any more common stuffs of mathematical logic be used in computation theory? Have someone summarize that?

Answer 1

This is not quite true. In fact I am nit-picking, but if you would like to be formal, then your definition is of the form

$$L = \{ \omega \mid \mathtt{pred}(\omega, A) \},$$

where $A$ is the automaton in question and $\mathtt{pred}(X,Y)$ is a binary predicate that says "automaton $Y$ accepts on $X$". An automaton is an automaton, not a predicate. You can use it for specifying sets, like many other objects, but by itself it is not a predicate (usually it is defined as some $k$-tuple).

To emphasize a difference, let me give you some other example. Consider a number $0$ and definition $$X = \{ x \mid \text{$x$ causes the $0$ to be the result of $f$ at $x$} \} = \{ x \mid f(x) = 0 \}.$$ I am aware that the above example is ridiculous, it was my intention. Now, by your argument I would call $0$ a predicate. However, it is just a natural number! Observe that if you would have some (context dependent) definition of a predicate that is in tight connection with $0$, then zero might be informally called a predicate. On the other hand, formally it is not a predicate.

To give you some more specific real-life situation, consider some set $Y$ and predicate $$\mathtt{y}(x) = x \in Y.$$ There is a 1-1 correspondence between sets and predicates of this form, i.e. any set can be transformed into a similar predicate, and any predicate (with some assumptions, e.g. given that the universe is a set) can be turned into a set by $Y = \{x \mid \mathtt{y}(x)\}$. Formally, neither $\mathtt{y}$ is a set, nor $Y$ is a predicate, but still we could informally call them such (some might argue that everything is a set, but I am not talking about this particular representation of $\mathtt{y}$).

And yes, as @Enjoys-Math already pointed out, theoretical computer science is full of logic, in fact almost any field uses it. The list is too long to write it down, but I can give you some examples:

• There is a whole area of logic-related computation, some more known examples include the programming language prolog.
• Semantics heavily uses logic and model theory.
• $\lambda$-calculus is pure applied logic; see also type theory, in particular Curry-Howard isomorphism.
• Many proofs of correctness, termination property and complexity of algorithms and uses mathematical logic.
• There is a computation model derived from logic circuits.

I hope that explains some things $\ddot\smile$