This question is about algorithmic problems, wHILE, and other notions of effective

computability.

$($a$)$ For EACH of the following problems, say whether it is a problem in our sense,

i$.$e$.$ an algorithmic problem. If it is not, explain briefly why not.

i$.$ Given an undirected graph where edges are annotated with distances $($as

integer numbers$),$ is there a path that visits all nodes of the graph that is no

longer than $234?$

ii$.$ Given the list of all integer numbers between $10$ and $1,000,000,$ does it

contain more than $999$ prime numbers?

$($b$)$ Which of the following notion$($s$)$ of computation can decide the same problems

as Turing Machines? No explanations required.

i$.$ Java Programs

ii$.$ Regular Expressions

iii. Cellular Automata

iv$.$ Untyped Lambda Expressions

$($c$)$ Give an example of a WHILE$-$statement list $S($written in core WHILE without

extensions$)$ such that:

$S|--\{x$:ulcornernurcorner,$Y$:ulcornermurcorner$\}\{x$:ulcornern$+2$murcorner,$Y$:ulcorner$0$urcorner$\}$

for all natural numbers $n$ and $m.$

$($d$)$ For which $$ can you make the following statement hold?

$x$:$=$ cons nil nil; while $x\{\}|--\{x$: nil $\}$

Explain your answer.

$($e$)$ Write a legal WHILE$-$program that translates into the following programs$-$as$-$data

notation: