In a course about Fundamental Computer Science, which includes Turing Machines,
how many questions like "Construct a Turing Machine that does X" should I include?
There should be at least a few basic constructions, like doubling a string of ones or checking whether a number is even, checking whether one number is larger than another, to show how a Turing Machine works. However, I'm unsure whether to include more difficult problems, like:
- Given two positive integers, check whether one is divisble by the other.
- Given a positive integer $n$, check whether $n$ is prime.
- Given a positive integer $n$, compute the $n$th Fibonnaci number.
- Given two positive integers $m,n$, calculate $m^n$.
Also, should I just allow the blank symbol and one other symbol or should I allow any number of symbols? Or maybe a mix. The difficulty will largely depend on this.
Students learn thinking abstractly about these problems. However, this abstract thinking is different from the abstract thinking that is used in most programming activities, so I'm unsure.