Acceptance Problem

The Acceptance problem is a decision problem asks if a given machine model can accept a formula. It is decidable for DFAs and NFAs

Problem Specification(s) §

Machine Models §

Given a machine $M$ and a string $w$, does $M$ accept $w$?

Generative Models §

Given a CFG

Decidability §

The decidability of the problem requires a restructuring. Let $L$ be a language given by the TM encodings of $M$ and $w$

$$A_k=\{⟨M,w⟩|\text{M is a machine of type k that accepts w}\}$$

Then, we need to check if $A_k$ is T-decidable.

DFA Acceptance Problem is decidable ^theorem-dfa

That is,

$$A_{DFA}=\{⟨M,w⟩|\text{M is a DFA that accepts w}\}\text{ is T-decidable}$$

Proof

The following is a proof by TM simulation Construct a multi-tape Turing machine, $T$, with 2 tapes (1 input and 1 work tape):

• For any string $s$, first check if $s$ is a valid encoding of the form $⟨M,w⟩$ and reject if not.
• Simulate $M$ using $T$ by:
• Write out the current configuration of $M$ using the work tape. This should record the current state of $M$ and the tape head ‘for $M$’ (how many characters has $M$ processed).
  • Initially this work tape would have $q_{0}0$. Then $q_{1}1$ (assuming in the DFA $M$, the first character of $w$ transitions it to $q_1$), etc.
• Use the transition function of $M$ to update the current configuration on the work tape.
• At every iteration, the counter of the tape head will always increase by one
• Eventually, the work tape will have $q_{k}n$ where $n$ is the size of $w$. If $q_k\in F_M$ (the accept states of $M$), accept. Else, reject.

NFA Acceptance Problem is decidable ^theorem-nfa

That is,

$$A_{NFA}=\{⟨N,w⟩|\text{N is a NFA that accepts w}\}\text{ is T-decidable}$$

Proof

Construct a multi-tape Turing machine, $T$, with 2 tapes (1 input and 1 work tape): We can solve this problem by using a proof by reduction to reduce this to the DFA acceptance problem (which is decidable).

• Again, first pre-process the string to check if it is of the correct form $⟨N,w⟩$.
• We know there exists an algorithm that converts a NFA to a DFA. By the Church-Turing Thesis, this means it can be done on a TM $T$. So we run $T$ first, ensuring we have the input string now in the form $⟨D,w⟩$ where $D$ is an equivalent DFA.
• Then we use the same procedure as the DFA version

TM Acceptance Problem is undecidable ^theorem-tm

That is:

$$A_{TM}=\{⟨T,w⟩|\text{T is a TM that accepts w}\}\text{ is recognisable, but not decidable}$$

Proof

This proof requires the assumption that some languages are unrecognisable. Let $L_s$ be the unrecognisable language constructed previously. Assume that $A_{TM}$ is decidable. Then there exists a Turing machine, $H$ that is a decider for it. For any $⟨M,w⟩$, we have:

$$H=\{\begin{array}{ll}\text{Accept},& \text{M accepts w}\\ \text{Reject},& \text{M does not accept w}\end{array}$$

Now construct a new Turing machine that simulates $H$, called $D$:

• $D$ only takes in one argument, that being a machine code, $⟨M⟩$.
• $D$ then simulates $H$ on $⟨M,⟨M⟩⟩$, that is, it uses $H$ to check if $M$ accepts $⟨M⟩$.
• If $H$ accepts, $D$ rejects, and vice versa (this makes $D$) a decider as well.
• So we have:

$$D=\{\begin{array}{ll}\text{Accept},& \text{H rejects ⟨M,⟨M⟩⟩ i.e. M does not accept ⟨M⟩}\\ \text{Reject},& \text{H accepts ⟨M,⟨M⟩⟩ i.e. M accepts ⟨M⟩}\end{array}$$

Then the language of $D$ is precisely the same as $L_s$:

$$L(D)=L_s=L_S=\{⟨M⟩|M\text{ does not accept }⟨M⟩\}$$

Which is proven to be unrecognisable. Thus, if we tried to feed in $⟨D,⟨D⟩⟩$ to $H$, because $L_s$ is unrecognisable, $H$ cannot decide it and thus cannot be a decider for the TM acceptance problem.

Reductions §

R1: The TM acceptance problem reduces to the Halting Problem

$$A_{TM}\le {\text{HALT}}_M$$

Proof

Recall that to prove this reduction, we need to show that can construct a decider for $A_{TM}$ given a decider for ${\text{HALT}}_M$. Let $H$ be the decider for ${\text{HALT}}_M$ (it takes in $⟨M,w⟩$ and decides if $M$ halts on $w$)

We can construct a new decider $S$ for $A_{TM}$ as follows:

• $S$ takes in the input $⟨M,w⟩$
• First, it simulates $H$ on $⟨M,w⟩$:
• If $H$ rejects, then $M$ does not halt on $w$ (it runs forever). Obviously this means that $M$ cannot accept $w$. So $S$ rejects as well.
• If $H$ accepts (and being a decider, it can only accept or reject), then $M$ always halts on $w$.
• Then, it is now ‘safe’ to simulate $M$ on $S$ (as we know $M$ terminates eventually)
• So $S$ accepts if $M$ accepts $w$
• And rejects if $M$ rejects $w$

Since $S$ always halts (is a decider) and decides if $M$ accepts $w$, we have constructed a decider for $A_{TM}$ and hence have proved the reduction.

R2: The TM acceptance problem reduces to the TM Emptiness Problem

$$A_{TM}\le {\text{EMPTY}}_{TM}$$

Proof

Recall that to prove this reduction, we need to show that can construct a decider for $A_{TM}$ given a decider for ${\text{EMTPY}}_{TM}$. Let $H$ be the decider for ${\text{EMPTY}}_{TM}$ (it takes in $⟨M⟩$ and decides if $M$ rejects every input)

We can construct a new decider $S$ for $A_{TM}$ as follows:

• $S$ takes in $⟨M,w⟩$
• Inside $S$, we construct a new Turing machine $T$ that takes in a string $x$ simulates $M$ independent of input:

$$T=\{\begin{array}{ll}\text{Accept},& \text{M accepts w}\\ \text{Reject},& \text{M rejects w}\\ \text{Run Forever},& \text{M runs forever }\end{array}$$

• Note that $T$ does not depend on $x$. It only depends on $M$ and $w$ which are ‘fixed’. Meaning, if $M$ accepts $w$, then $T$ accepts everything. If $M$ rejects $w$, $T$ rejects everything. Thus:
• Thus:

$$L(T)=\{\begin{array}{ll}{\Sigma }^{\ast },& \text{M accepts w}\\ \varnothing ,& \text{M rejects w}\\ \varnothing ,& \text{M runs forever}\end{array}$$

• Then, we run the emptiness decider $H$ on $T$. Since $H$ accepts when $L(T)=\varnothing$, this means that $M$ either rejects $w$ or runs forever (in either case, it does not accept $w$). If $H$ rejects, then $L(T)={\Sigma }^{\ast }$ so $M$ accepts $w$

Thus, we have created a decider $S$ (since $H$ is a decider) that decides if $M$ accepts $w$. So we have proven the reduction.

Applications §

• If the TM acceptance problem, $A_{TM}$ was decidable, it would imply that satisfiability in predicate logic would be decidable (since the decider could be converted into an algorithm)
• The TM acceptance problem, $A_{TM}$ is useful in static code analysis, as it can determine if a given program satisfies its specifications (accepts some input strings) without actually running the program. It also helps identify security vulnerabilities and runtime errors.
  • This has critical applications in defence and medicine
• Since the DFA acceptance problem, $A_{DFA}$ is decidable, any program that can be modelled as an equivalent DFA can be ‘checked’ by a Turing machine.