English subtitles

← Computation in Complex Systems: Computation Everywhere : Turing Machines Quiz

Get Embed Code
1 Language

Showing Revision 1 created 07/19/2020 by Alexis McMillan-Clifton.

  1. So,
  2. here is a quiz for you
  3. to get your feet wet
  4. in designing Turing machines.
  5. Suppose I have an alphabet
  6. which is just zero, one,
  7. and a special symbol,
  8. a dot,
  9. which we can think of as a decimal point,
  10. or I guess whatever you call you call
  11. decimal points in binary,
  12. a binary point.
  13. Suppose the machine starts there,
  14. I would like you to write a little machine
  15. which computes
  16. the successor function.
  17. I want it to start at that binary point
  18. and then move to the left,
  19. reading those zeroes and ones,
  20. doing something to them,
  21. and then returning to its starting point,
  22. and I want it to update
  23. whatever binary integer is written there
  24. to the left of the binary point,
  25. from x to x+1, add one to it.
  26. And, maybe this is too big of a hint,
  27. but I suggest that you give it
  28. three states, called carry,
  29. return, and halt.
  30. All right. So figure out what the
  31. transitions for this little
  32. Turing machine should be.