Problem 2
Write a Bare Bones program that places a 1 in the variable \(Z\) if the variable \(X\) is less than or equal to the variable \(Y\), and places a 0 in the variable \(\mathrm{Z}\) otherwise.
Problem 3
Write a Bare Bones program that places the Xth power of 2 in the variable \(Z\).
Problem 4
In each of the following cases, write a program sequence in Bare Bones that performs the indicated activity: a. Assign 0 to \(Z\) if the value of \(X\) is even; otherwise assign 1 to \(\mathrm{Z}\). b. Calculate the sum of the integers from 0 to \(X\).
Problem 6
Describe the function computed by the following Bare Bones program, assuming the function's inputs are represented by \(X\) and \(Y\) and its output by \(Z\) : copy X to Z copy Y to Aux while Aux not 0: decr Z decr Aux
Problem 12
Give an example of a language that is not deterministic.
Problem 13
Design a Turing machine that recognizes the set of palindromes in \(\\{a, b\\}^{*}\) such that the number of instances of the letter a is a multiple of three.
Problem 14
Suppose a pattern of 0 s and 1 s on the tape of a Turing machine is delimited by asterisks at either end. Design a Turing machine that rotates this pattern one cell to the left, assuming that the machine starts with the current cell being the asterisk at the right end of the pattern.
Problem 15
Design a Turing machine that places 0 s and \(1 \mathrm{~s}\) in all the cells to the right of the current cell until it reaches a cell containing a plus symbol.
Problem 16
Summarize the Church-Turing thesis.
Problem 17
Is the following Bare Bones program self-terminating? Explain your answer. copy X to Y incr Y incr Y while X not 0: decr X decr X decr Y decr Y decr Y while Y not 0: incr X decr Y while X not 0:
