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} = { \langle M,w \rangle \ \vert \ \text{$M$ is a DFA that accepts $w$} } \text{ is T-decidable}

>[!example]- Proof > The following is a proof by [TM simulation](Turing%20Machine%20Simulation.md) > Construct a [multi-tape Turing machine](Multi-tape%20Turing%20Machine.md), $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 $\langle M,w \rangle$ 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} = { \langle N,w \rangle \ \vert \ \text{$N$ is a NFA that accepts $w$} } \text{ is T-decidable}

>[!example]- Proof > Construct a [multi-tape Turing machine](Multi-tape%20Turing%20Machine.md), $T$, with 2 tapes (1 input and 1 work tape): >We can solve this problem by using a [proof by reduction](Proof%20By%20Reduction.md) 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 $\langle N,w \rangle$. >* We know there exists an algorithm that converts a [NFA to a DFA](Determinisation%20Of%20NFAs.md). By the [Church-Turing Thesis](Church-Turing%20Thesis.md), 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 $\langle D,w \rangle$ where $D$ is an equivalent DFA. >* Then we use the same procedure as the [DFA version](#^theorem-dfa)

TM Acceptance Problem is undecidable ^theorem-tm

That is:

A_{TM} = { \langle T,w \rangle \ \vert \ \text{$T$ is a TM that accepts $w$} } \text{ is recognisable, but not decidable}

$$>[!example]-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 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$)

Recall that to prove this

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 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)

Recall that to prove this

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.