<p>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):</p>

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

<p>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.</p>

CC BY-SA 3.0
2016-08-25T12:58:20.213Z
2016-08-25T12:58:20.213Z
Klaus Draeger
<p>Is there a Turing machine that can evaluate arithmetic operations with brackets containing <code>+</code>, <code>-</code>, and <code>*</code> operations that are applied to integer numbers?</p>

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

<pre><code>7*((3 + 11)*2 -23) + 2*(2 - 4)
</code></pre>

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

CC BY-SA 3.0
2016-08-25T15:45:34.993Z
This question is not research-level and fits better on cs.stackexchange.com.
Andrej Bauer
<turing-machines><universal-turing-machines>
Where can I find a Turing machine evaluating arithmetic expressions?
Roman
# Where can I find a Turing machine evaluating arithmetic expressions?

(Asked by: username_0 on 2016-08-25)

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.

**Tags:** turing-machines, universal-turing-machines
> **Comments:**
> **username_1**: This question is not research-level and fits better on cs.stackexchange.com.  

---

## 1 answers

### Answer by username_2 on 2016-08-25. Score: 1 | Accepted answer

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.


---

