Stick arithmetic is probably the easiest to implement with a Turing machine. The collection to use is C={ \u2610, |, X, =, +}.<\/p>\n
We write an addition on the strip with sticks, for example: ||||+||=<\/p>\n
The result should be of the form: ||||+||=||||||<\/p>\n
Start on the = sign or on the stick immediately to the right, as you wish. End on the first blank to the right of the answer.<\/p>\n\nDescription<\/summary>\n
The head first goes to the left. If it encounters an X, the + sign, or the = sign, it continues left. If it encounters a stick, it transforms it into an X and moves right until it encounters a blank. There, it writes an X and begins moving left again. If it encounters a blank while going left, it returns to the right, transforming all the Xs into sticks, and stops at the first blank.<\/p>\n<\/details>\n
Universal decrement of a natural number<\/h1>\n
We often need to evaluate the value of a number, and the easiest way to do this with the Turing machine is to decrement<\/em> the number. We are going to create a Turing machine that can be reused in larger programs. This involves decrementing a natural number placed on the tape by one digit per square. If the integer reaches its final value, 0, then the 0 must be erased; if there are several consecutive 0s remaining, they must all be erased. The program must<\/em> stop on the last digit, or on the last blank it has written if it has erased everything. Why? Because another program that uses our machine must “know” whether the machine has performed a decrement or not. As long as it stops on a digit, it means that the decrement has taken place. If it stops on a blank, it means that the decrement is complete. This is how our machine passes the information to the calling machine.<\/p>\n
Our machine must also allow for the possibility that there may be signs other than blanks on either side of the number. We therefore prefer to use the sign \u2200 to identify any sign other than the digits.<\/p>\n
Here are some examples; the position of the head indicates the starting point and the ending point.<\/p>\nHead positions before and after treatment.<\/figcaption><\/figure>\n\nSolution: The Decrement Machine (spoiler)<\/summary>\n
Machine: [Decrementer] \n# Decrements a natural number. If there are any remaining 0s, replace them with blanks. Always stops on the last digit, or the blank. \n# Start: on the rightmost data item \n# End: on the rightmost data item<\/p>\n
State: erase9 \n# Erases all consecutive 9s; stops on the last blank. \nerase9, 9 , \u2610 , \u2192 , erase9 \nerase9, \u2200 , \u2200 , \u2190 , stop<\/p><\/blockquote>\n<\/details>\n
Place N apples!<\/h1>\n
In some cases, you need a large number of objects on the tape to test a program. For example, you would need 100 apples to check whether a counting program goes from 1 to 100. Of course, if you have time to waste, you can manually place the apples one by one on the tape and test the program.<\/p>\n
But we can also create a Turing program! We write a natural number greater than 0 on the tape, the head is placed on the last digit.<\/p>\n
And here is the final situation: the head stops on the first apple in a series. The number originally written on the strip is erased. The apples are placed to the right of the initial number.<\/p>\n
<\/p>\n
Convenient, isn’t it? To run the program, once the debugging phase has been completed, we recommend using the fastest operating mode – the “horse to finish” button, for example. Execution time increases rapidly with the number of apples.<\/p>\n
c= {[0-9],\u2610,apple}<\/p>\n\nSolution 1: Everything in the same machine (spoiler).<\/summary>\n
Machine: [Repeater] \n# Decrements a natural number and places that many apples to the right of that number. \nState: Decrement \n# Decrements a number \nDecrement, 9 , 8 , \u2192 , TransitRight \nDecrement, 8 , 7 , \u2192 , TransitRight \nDecrement, 7 , 6 , \u2192 , TransitRight \nDecrement, 6 , 5 , \u2192 , TransitRight \nDecrement, 5 , 4 , \u2192 , TransitRight \nDecrement, 4 , 3 , \u2192 , TransitRight \nDecrement, 3 , 2 , \u2192 , TransitRight \nDecrement, 2 , 1 , \u2192 , TransitRight \nDecrement, 1 , 0 , \u2192 , TransitRight \nDecrement, 0 , 9 , \u2190 , Decrement \nDecrement, \u2610 , \u2610 , \u2192 , Delete9 \nState: Delete9 \n# Deletes all 9s and stop. \nDelete9, 9 , \u2610 , \u2192 , Delete9 \nState: TransitRight \nTransitRight, \u2610 , apple , \u2190 , TransitLeft \nTransitRight, \u2200 , \u2200 , \u2192 , TransitRight \nState: TransitLeft \nTransitLeft, apple , apple , \u2190 , TransitLeft \nTransitLeft, \u2200 , \u2200 , Decrement<\/p><\/blockquote>\n<\/details>\n\nSolution 2: two machines, the one that decrements is a repeat of the previous exercise (spoiler)<\/summary>\n
Machine: [AddApples] \n# Start: on the rightmost data \n# End: on the rightmost data<\/p>\n
State: addApple \n# Adds an apple to the next apple string, if there is room. \naddApple, apple , apple , \u2192 , addApple \naddApple, \u2610 , apple , \u2190 , backBack<\/p>\n
State: Backspace \n# Backspaces to the initial number. \nBackspace, apple , apple , \u2190 , Backspace \nbackspace, \u2200 , \u2200 , startDecrementer \n#\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014 \nMachine: [Decrementer] \n# Decrements a natural number. If there are any 0s left, replace them with blanks. Always stops on the last digit, or the blank. \n# Start: on the rightmost data item \n# End: on the rightmost data item<\/p>\n
State: erase9 \n# Erases all consecutive 9s; stops on the last blank. \nerase9, 9 , \u2610 , \u2192 , erase9 \nerase9, \u2200 , \u2200 , \u2190 , stop<\/p><\/blockquote>\n<\/details>\n
Move a natural number to the left<\/h1>\n
Even though the formatting possibilities are very limited on our tape, presentation matters! Often, after a series of conversions, we need to move the result, a natural number, to a new position, usually immediately to the right of an = sign. To make things more difficult, we assume that anything<\/em> can exist between the number and the = sign, including digits that are not part of the number to be transferred.<\/em> When moving, all signs present between the number and the = sign must be erased (i.e., replaced by a blank). The machine must stop on the = sign. Here, the symbol \u2200 will be of great help. Initially, the head must be positioned on the first digit forming the number to be moved (i.e., the left-hand digit). Finally, it must be positioned on the “=” sign.<\/p>\n
Example: starting situation: =\u2610 1 2 3 xyzt 5 8 4\u2610 \u2610 \u2610 ( head positioned on 5: move 584)<\/em><\/p>\n
Obviously, the machine shouldn’t crash if the number is already correctly positioned after the = sign. And if you use my X and Y technique described below, it shouldn’t crash if there’s only one box between the = and the first digit.<\/p>\n
The collection is C={the entire collection of signs defined on Actilud}.<\/p>\n
Here, we will have to memorize<\/em> the numbers that we move. With the Turing machine, the only possibility of memorizing information is to use a state for each piece of information to be memorized<\/em> . Among the states necessary for operation, we will have to create as many as there are signs to be transported, i.e. 10.<\/p>\n
Here, we have to memorize the digits we move. With the Turing machine, the only way to memorize information is to use a state for each piece of information to be memorized. We’ll need to create as many states as there are signs to be transported, i.e. 10, in addition to the other states.<\/p>\n
Of course, there are several ways to implement the program. Programming certain states is quite repetitive; so, to save the number of states to program, my idea was the following. First, we clean the strip between the = sign and the first number. We delimit the space between the = and the first number with two letters, X and Y. The segment [X,Y] moves as we move a number after those already placed to the right of =. The letter Y allows us to test the end of the program: if there are no more numbers to the right of Y, it’s over. X marks the location of the box in which we must place a number. If we don’t use this trick, we have to create 10 additional states just to place a number to the right of the = sign! (note that instead of using X and Y, we could have used only X).<\/p>\n
Of course, there are several ways of implementing the program. Programming certain states is rather repetitive; so, to save the number of states to be programmed, my idea was as follows. First, we clean up the strip between the = sign and the first digit. The space between the = and the first digit is delimited by two letters, X and Y. The segment [X,Y] moves as you move a digit following those already placed to the right of =. The letter Y is used to test the end of the program: if there are no more digits to the right of Y, it’s over. X marks the location of the box in which to place a digit. If you don’t use this trick, you’ll need to create 10 additional states just to place a digit to the right of the = sign! (note that instead of using X and Y, we could have used X only).<\/p>\n\nHere is the listing (spoiler)<\/summary>\n
Machine: [MoveNumberToEqualLeft] \n# Start: on the leftmost digit of the number to be transferred \n# End: on the = sign<\/p>\n
State: initialize \n# Leave the pointed digit to prepare the tape \ninitialize, \u2200 , \u2200 , \u2190 , fill blanks<\/p>\n
State: fill in blanks \n# Fill the boxes to the left with blanks up to the sign = \nfill in blanks, ‘=’ , ‘=’ , \u2192 , set X \nfill in blanks, \u2200 , \u2610 , \u2190 , fill in blanks<\/p>\n
State: set X \n# After finding the = or dropping a number, drop an x \u200b\u200band go looking for the Y or a number. \nset X, \u2610 , X , \u2192 , search Y \nset X, Y , X , \u2192 , pickNumber \nset X, \u2200 , \u2200 , \u2190 , return to equal<\/p>\n
State: takeNumber \n# If a number is found, enters the corresponding move state. Otherwise, return to equal and stop. \ntakeNumber, 0 , Y , \u2190 , move0 \ntakeNumber, 1 , Y , \u2190 , move1 \ntakeNumber, 2 , Y , \u2190 , move2 \ntakeNumber, 3 , Y , \u2190 , move3 \ntakeNumber, 4 , Y , \u2190 , move4 \ntakeNumber, 5 , Y , \u2190 , move5 \ntakeNumber, 6 , Y , \u2190 , move6 \ntakeNumber, 7 , Y , \u2190 , move7 \ntakeNumber, 8 , Y , \u2190 , move8 \ntakeNumber, 9 , Y , \u2190 , move9 \ntakeNumber, \u2200 , \u2200 , \u2190 , return on equal<\/p>\n
State: search Y \n# Searches for the Y previously placed on the strip. If a number is found in place of the Y, go to the Take Number state without moving. If the Y is found, delete it, go right and go to the Take Number state. \nsearch Y, \u2610 , \u2610 , \u2192 , search Y \nsearch Y, Y , \u2610 , \u2192 , takeNumber \nsearch Y, 0 , 0 , takeNumber \nsearch Y, 1 , 1 , takeNumber \nsearch Y, 2 , 2 , takeNumber \nsearch Y, 3 , 3 , \ntakeNumber search Y, 4 , 4 , takeNumber \nsearch Y, 5 , 5 , \ntakeNumber search Y, 6 , 6 , \ntakeNumber search Y, 7 , 7 , takeNumber \nsearch Y, 8 , 8 , takeNumber \nsearch Y, 9 , 9 , takeNumber<\/p>\n
State: return on equal \nreturn on equal, \u2610 , \u2610 , \u2190 , return on equal \nreturn on equal, X , \u2610 , \u2190 , return on equal \nreturn on equal, ‘=’ , ‘=’ , stop \nreturn on equal, 0 , 0 , \u2190 , return on equal \nreturn on equal, 1 , 1 , \u2190 , return on equal \nreturn on equal, 2 , 2 , \u2190 , return on equal \nreturn on equal, 3 , 3 , \u2190 , return on equal \nreturn on equal, 4 , 4 , \u2190 , return on equal \nreturn on equal, 5 , 5 , \u2190 , return on equal \nreturn on equal, 6 , 6 , \u2190 , return on equal \nreturn on equal, 7 , 7 , \u2190 , return on equal \nreturn on equal, 8 , 8 , \u2190 , return on equal \nreturn on equal, 9 , 9 , \u2190 , return on equal<\/p>\n
State: move0 \nmove0, \u2610 , \u2610 , \u2190 , move0 \nmove0, X , 0 , \u2192 , drop X<\/p>\n
State: move1 \nmove1, \u2610 , \u2610 , \u2190 , move1 \nmove1, X , 1 , \u2192 , drop X<\/p>\n
State: move2 \nmove2, \u2610 , \u2610 , \u2190 , move2 \nmove2, X , 2 , \u2192 , drop X<\/p>\n
State: move3 \nmove3, \u2610 , \u2610 , \u2190 , move3 \nmove3, X , 3 , \u2192 , drop X<\/p>\n
State: move4 \nmove4, \u2610 , \u2610 , \u2190 , move4 \nmove4, X , 4 , \u2192 , drop X<\/p>\n
State: move5 \nmove5, \u2610 , \u2610 , \u2190 , move5 \nmove5, X , 5 , \u2192 , drop X<\/p>\n
State: move6 \nmove6, \u2610 , \u2610 , \u2190 , move6 \nmove6, X , 6 , \u2192 , drop X<\/p>\n
State: move7 \nmove7, \u2610 , \u2610 , \u2190 , move7 \nmove7, X , 7 , \u2192 , drop X<\/p>\n
State: move8 \nmove8, \u2610 , \u2610 , \u2190 , move8 \nmove8, X , 8 , \u2192 , drop X<\/p>\n
State: move9 \nmove9, \u2610 , \u2610 , \u2190 , move9 \nmove9, X , 9 , \u2192 , drop X<\/p>\n
Adding sticks Stick arithmetic is probably the easiest to implement with a Turing machine. The collection to use is C={ \u2610, |, X, =, +}. We write an addition on the strip with sticks, for example: ||||+||= The result should be of the form: ||||+||=|||||| Start on the = sign or on the stick immediately […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-297","post","type-post","status-publish","format-standard","hentry","category-turing-machine-the-challenges"],"_links":{"self":[{"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/posts\/297","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/comments?post=297"}],"version-history":[{"count":4,"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/posts\/297\/revisions"}],"predecessor-version":[{"id":301,"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/posts\/297\/revisions\/301"}],"wp:attachment":[{"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/media?parent=297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/categories?post=297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/actilud.com\/info\/en\/wp-json\/wp\/v2\/tags?post=297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"](\"https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/03\/turing_decrementer.png\")
![\"\"](\"https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/03\/turing_pommes4.png\")
<\/p>\n