How do I do a subtraction question on turing machine

Question

For example, 111-11

I want to have the output as 111-11=1

I am a beginner at TM and am having a hard time trying to solve this question.

Answer 1

It seems that you have unary numbers, so there are three cases to consider: number you subtract from is greater, uqual or smaller, this gives you hint what to handle.

In unary when you subtract 11 from 111 (111 - 11 = 1) you have to delete ones in minuend until subtrahend is 0.
In case these are equal, you have to denote 0 (empty tape might denote this). In the third case, result is negative.

Case 1) 111 - 11 = 11 - 1 = 1 - 0 = 1
Case 2) 111 - 111 = 11 - 11 = 1 - 1 = 0 - 0 = 0
Case 3) 11 - 111 = 1 - 11 = 0 - 1 = - 1

So let us start with first phase: start with scratching from both sides, call it say qS:
'B111-11B' where B is blank, on qS put B at leftmost 1, switch state to qS1, which goes right until it finds B. Moves one to the left, if it is 1, put B and return to the leftmost 1 (say state qSr). After execution:
'BB11-1BB' repeat
'BBB1-BBB' if in state qS1 there is no 1 but -, put B on - and accept.

Case 2 would yield something like 'BB-BB', if you are happy with Blank tape as 0, case 1 solves it already, otherwise put 0 on the tape if there are no 1 left.

Case 3 leaves you with situation like 'B1-11B'. Here only modification is to accept when after - there is Blank. So one step later, there is 'BB-1BB', this is result already.

What could go wrong?
There might be input like 'B11-1-1B', if you are not promised it won't happen. In such case split going right in qS1 into find '-' and then find Blank. If after first '-' there occurs another one, reject on it.

To practice more you could write your code in simulator online, check addition first as Apass.Jack suggested. When you finish, try multiplication, the sooner the better.

To see a working version look at my subtraction code at simulator.

This code has format:
state read_symbol write_symbol direction new_state, everything after semicolon is a comment, halt-accept is accepting state, halt-reject is rejecting state * in direction is not move instruction (you may be familiar with S notation or do not really care how it moves, since machine halts now).

qS 1 _ R qS1 ; state to start scratching left to -
qS - - R q2 ; check if there is 1 after 1 
qS1 1 1 R qS1 ; pass through 1
qS1 - - R qS2 ; minus found
qS2 1 1 R qS2 ; going for rightmost 1
qS2 _ _ L qSr ; blank found after all 1
qS2 - - * halt-reject ; second minus found, reject bad formatted input
qSr 1 _ L qSr2 ; scratch last 1
qSr - 1 * halt-accept ; scratched 1 at the beginning appears here.
qSr2 1 1 L qSr2 ; leave 1 as is
qSr2 - - L qSr2 ; leave - as is
qSr2 _ _ R qS ; start another pass

q2 1 1 R q2c ; there is a - but still input may be malformed, check it

q2c 1 1 R q2c;
q2c - - * halt-reject ; found second -, reject
q2c _ _ * halt-accept ; there is negative number on tape, accept

q2 _ _ L q2m ; there is only minus left, clean it up
q2 - - * halt-reject ; malformed
q2m - 0 * halt-accept ; accept after cleanup

; tested on accepting -, 1-, -1, 1-1, 11-1, 111-1, 1-11
; testet on rejecting 1--1, 11-11-, --, -1
; to explore it more, maybe -11-11 should give -1111? Not handled now