Turing Machine for addition Last Updated : 11 Jul, 2025 Comments Improve Suggest changes 29 Likes Like Report Prerequisite - Turing Machine A number is represented in binary format in different finite automata. For example, 5 is represented as 101. However, in the case of addition using a Turing machine, unary format is followed. In unary format, a number is represented by either all ones or all zeroes. For example, 5 will be represented by a sequence of five zeroes or five ones: 5 = 1 1 1 1 1 or 5 = 0 0 0 0 0. Lets use zeroes for representation. A Turing machine can be designed to perform addition by using its tape to represent the numbers to be added and its states to control the addition process. Here's a high-level description of the process: The two numbers to be added are placed on the tape, separated by a blank symbol.The Turing machine starts at the leftmost digit of the first number and moves to the right, one digit at a time, checking the value of each digit. If a digit is 0, the machine writes a 0 in the corresponding position of the sum. If it's 1, it writes a 1.If both digits are 1, the machine writes a 0 and adds a carry of 1 to the next position.When the Turing machine reaches the end of the input, it adds any remaining carry and writes the result on the tape. For adding 2 numbers using a Turing machine, both these numbers are given as input to the Turing machine separated by a "c". Examples - (2 + 3) will be given as 0 0 c 0 0 0: Input : 0 0 c 0 0 0 // 2 + 3 Output : 0 0 0 0 0 // 5 Input : 0 0 0 0 c 0 0 0 // 4 + 3 Output : 0 0 0 0 0 0 0 // 7 Approach used - Convert a 0 in the first number in to X and then traverse entire input and convert the first blank encountered into 0. Then move towards left ignoring all 0's and "c". Come the position just next to X, and repeat the same procedure until the time we get a "c" instead of X on returning. Convert the c into blank and addition is completed. Steps - Step-1: Convert 0 into X and go to step 2. If symbol is "c" then convert it into blank(B), move right and go to step 6. Step-2: Keep ignoring 0's and move towards right. Ignore "c", move right and go to step 3. Step-3: Keep ignoring 0's and move towards right. Convert a blank (B) into 0, move left and go to step 4. Step-4: Keep ignoring 0's and move towards left. Ignore "c", move left and go to step 3. Step-5: Keep ignoring 0's and move towards left. Ignore an X, move right and go to step 1. Step-6: End. Comment R RishabhMalik Follow 29 Improve R RishabhMalik Follow 29 Improve Article Tags : Misc GATE CS Theory of Computation Explore Automata _ IntroductionIntroduction to Theory of Computation5 min readChomsky Hierarchy in Theory of Computation2 min readApplications of various Automata4 min readRegular Expression and Finite AutomataIntroduction of Finite Automata3 min readArden's Theorem in Theory of Computation6 min readSolving Automata Using Arden's Theorem6 min readL-graphs and what they represent in TOC4 min readHypothesis (language regularity) and algorithm (L-graph to NFA) in TOC7 min readRegular Expressions, Regular Grammar and Regular Languages7 min readHow to identify if a language is regular or not8 min readDesigning Finite Automata from Regular Expression (Set 1)4 min readStar Height of Regular Expression and Regular Language3 min readGenerating regular expression from Finite Automata3 min readCode Implementation of Deterministic Finite Automata (Set 1)8 min readProgram for Deterministic Finite Automata7 min readDFA for Strings not ending with "THE"12 min readDFA of a string with at least two 0âs and at least two 1âs3 min readDFA for accepting the language L = { anbm | n+m =even }14 min readDFA machines accepting odd number of 0âs or/and even number of 1âs3 min readDFA of a string in which 2nd symbol from RHS is 'a'10 min readUnion Process in DFA4 min readConcatenation Process in DFA3 min readDFA in LEX code which accepts even number of zeros and even number of ones6 min readConversion from NFA to DFA5 min readMinimization of DFA7 min readReversing Deterministic Finite Automata4 min readComplementation process in DFA2 min readKleene's Theorem in TOC | Part-13 min readMealy and Moore Machines in TOC3 min readDifference Between Mealy Machine and Moore Machine4 min readCFGRelationship between grammar and language in Theory of Computation4 min readSimplifying Context Free Grammars6 min readClosure Properties of Context Free Languages11 min readUnion and Intersection of Regular languages with CFL3 min readConverting Context Free Grammar to Chomsky Normal Form5 min readConverting Context Free Grammar to Greibach Normal Form6 min readPumping Lemma in Theory of Computation4 min readCheck if the language is Context Free or Not4 min readAmbiguity in Context free Grammar and Languages3 min readOperator grammar and precedence parser in TOC6 min readContext-sensitive Grammar (CSG) and Language (CSL)2 min readPDA (Pushdown Automata)Introduction of Pushdown Automata5 min readPushdown Automata Acceptance by Final State4 min readConstruct Pushdown Automata for given languages4 min readConstruct Pushdown Automata for all length palindrome6 min readDetailed Study of PushDown Automata3 min readNPDA for accepting the language L = {anbm cn | m,n>=1}2 min readNPDA for accepting the language L = {an bn cm | m,n>=1}2 min readNPDA for accepting the language L = {anbn | n>=1}2 min readNPDA for accepting the language L = {amb2m| m>=1}2 min readNPDA for accepting the language L = {am bn cp dq | m+n=p+q ; m,n,p,q>=1}2 min readConstruct Pushdown automata for L = {0n1m2m3n | m,n ⥠0}3 min readConstruct Pushdown automata for L = {0n1m2n+m | m, n ⥠0}2 min readNPDA for accepting the language L = {ambncm+n | m,n ⥠1}2 min readNPDA for accepting the language L = {amb(m+n)cn| m,n ⥠1}3 min readNPDA for accepting the language L = {a2mb3m|m>=1}2 min readNPDA for accepting the language L = {amb2m+1 | m ⥠1}2 min readNPDA for accepting the language L = {aibjckdl | i==k or j==l,i>=1,j>=1}3 min readConstruct Pushdown automata for L = {a2mc4ndnbm | m,n ⥠0}3 min readNPDA for L = {0i1j2k | i==j or j==k ; i , j , k >= 1}2 min readNPDA for accepting the language L = {anb2n| n>=1} U {anbn| n>=1}2 min readNPDA for the language L ={wÐ{a,b}* | w contains equal no. of a's and b's}3 min readTuring MachineTuring Machine in TOC7 min readTuring Machine for addition3 min readTuring machine for subtraction | Set 12 min readTuring machine for multiplication2 min readTuring machine for copying data2 min readConstruct a Turing Machine for language L = {0n1n2n | nâ¥1}3 min readConstruct a Turing Machine for language L = {wwr | w ∈ {0, 1}}5 min readConstruct a Turing Machine for language L = {ww | w ∈ {0,1}}7 min readConstruct Turing machine for L = {an bm a(n+m) | n,mâ¥1}3 min readConstruct a Turing machine for L = {aibjck | i*j = k; i, j, k ⥠1}2 min readTuring machine for 1's and 2âs complement3 min readRecursive and Recursive Enumerable Languages in TOC6 min readTuring Machine for subtraction | Set 22 min readHalting Problem in Theory of Computation4 min readTuring Machine as Comparator3 min readDecidabilityDecidable and Undecidable Problems in Theory of Computation6 min readUndecidability and Reducibility in TOC5 min readComputable and non-computable problems in TOC6 min readTOC Interview preparationLast Minute Notes - Theory of Computation13 min readTOC Quiz and PYQ's in TOCTheory of Computation - GATE CSE Previous Year Questions2 min read Like