Is there a Turing machine that can evaluate arithmetic operations with brackets containing +, -, and * operations that are applied to integer numbers?

For example, it should be able to evaluate the following expression given as a sequence of symbols:

7*((3 + 11)*2 -23) + 2*(2 - 4)

I know that such a Turing machine should exists. However, I cannot find any implementation of such a machine.


closed as off-topic by Andrej Bauer, Hsien-Chih Chang 張顯之, Mohammad Al-Turkistany, Marzio De Biasi, David Eppstein Aug 27 '16 at 0:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Andrej Bauer, Hsien-Chih Chang 張顯之, Mohammad Al-Turkistany, Marzio De Biasi, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This question is not research-level and fits better on cs.stackexchange.com. $\endgroup$ – Andrej Bauer Aug 25 '16 at 15:45

Probably the main reason why you don't find such a machine is its complexity - most textbooks try to not overwhelm the reader with details. We can give a sketch of how to construct it, however. Note that I will make a simplifying assumption, namely that (unlike your example) the expressions are fully parenthesized. I also assume that we already have Turing machines implementing the individual arithmetic operations, as well as standard auxiliary ones like copy and find. Then the main loop of our machine looks like this (starting on the first input symbol as usual):

  1. Move right until you find a ')' or the end of the input; if the latter, the expression is fully evaluated, and we are done.
  2. Mark the ')', go back to the left to find the matching '(', mark it as well.
  3. Create a copy of the prefix before the marked '(' behind the input.
  4. Find the operator between the marked parentheses, branch to a Turing machine performing the corresponding operation, depositing the result behind the copied prefix.
  5. Copy the suffix after the marked ')' after the result from 4.
  6. Go back, delete the original input, place the head on the first copied symbol, and go to 1.

Essentially, this machine keeps producing simplified versions of the expression by evaluating the leftmost innermost operator on its arguments, replacing the subexpression by the result.


Not the answer you're looking for? Browse other questions tagged or ask your own question.