| HPS 0628 | Paradox | |
Back to doc list
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 on some possible input.
(a) Is this an achievable boast? Explain.
(b) Does your answer to (a) change if the boast restricts itself to programs of up to a hundred billion lines of code?