How do you argue (or prove) that a certain Turing machine accepts a language?

Question

I have an existing Turing machine that is essentially the same as this one here:

X is the blank symbol, # is the end of the tape. The format is input/output, direction. 0 indicates failure (parentheses not correctly nested) and 1 success (correctly nested parentheses).

How would you go about arguing that the language that it is supposed to accept (correctly nested parentheses) is actually accepted? You don´t need to provide specific solutions to this problem, but any pointers on how to go about solving this kind of thing would be great!

Thanks.

Answer 1

You can prove it by induction on the length of the input string.

I’d use the minimal counterexample form of induction.

• Suppose that $w$ is a matched string of minimal length that is not accepted; it’s not hard to show that the machine blanks out the first adjacent () pair and starts over at the end of any initial string of left parentheses, and that it then proceeds essentially as if it had been fed the resulting string initially. I say essentially because it doesn’t actually start at the beginning of the string, and the string now has a couple of embedded blanks. However, you can easily show that embedded blanks are ignored and that the difference in starting points doesn’t affect the outcome. To complete this half of the proof, you need only show that deleting the first () pair of a matched parenthesis string leaves a matched string, contradicting the minimality of $w$. This is easy if you know the standard characterization: a string is matched iff it has the same number of left and right parentheses, and each initial segment has at least as many left as right parentheses.

• Now suppose that $w$ is an unmatched string of minimal length that is accepted, and get a similar contradiction: the machine must find a first () pair, since $w$ is accepted, and you can show that its removal must leave an unmatched string.