Back to doc list

Assignment 11.
Uncomputable Tasks

For submission

1. A Turing machine can compute functions on the natural numbers. Consider the task of translating an arbitrary, but finite passage of English into German. Is this a task that can be represented as a function from natural numbers to natural numbers? Explain.

2. Consider an ordinary desktop computer that has been enhanced so that it has unlimited memory and can execute programs of arbitrarily large, but finite size. According to the Church-Turing thesis, what can this enhanced computer do that a Turing machine cannot. Explain.

3. A new computer language comes with a debugger that guarantees that it will warn you (always correctly) ahead of time if any program you write, no matter how long, will crash when you feed the program some input freely selected by you.

(a) Is this an achievable boast? Explain.

(b) Does your answer to (a) change if the boast restricts itself to programs and inputs of up to a hundred billion lines of code?

For discussion

Not for submission

A. What other abstract models of a computer might we consider? Is the model of a Turing machine and its equivalent forms too narrow?

B. What might it take to have a computer that can do things no Turing machine can do?

C. There are infinitely many more uncomputable tasks than there are computable tasks. How worrisome is this? What if we change the question to "How many interesting uncomputable tasks are there?"

D. A new computer language system is advertised as allowing novices to assemble computer programs using simple boxes and arrows. It assures novices that it is impossible to use the system to write programs that crash. Given the restrictions of the halting problem, how might it be possible for the assurance to be correct?