Problem 5: Representing Numbers with Algorithms (15 points). In performing arith
ID: 3698299 • Letter: P
Question
Problem 5: Representing Numbers with Algorithms (15 points). In performing arithmetic on a computer, one often faces the problem of representing numbers. For numbers with a finite decimal representation, say 270.072, this is easy: we simply output the decimal representation as a string of finite length. However, in many cases we wish to represent a number with infinitely many digits in its decimal representation; for example, 1/3 = 0.3333333 . . ., 1/7 = 0.142857 . . ., = 3.14159..., or e = 2.71828.... There are a number of solutions to this problem, each with its advantages and disadvantages, but for the sake of this problem we will focus on representing a number via an algorithm.
For a nonnegative real number x R+, we denote its decimal representation by x0.x1x2x3 ... where x0 is the integer part of x, and xi is the i’th digit in the fractional part of x. For example, if x = 10 + = 13.14159... we have x0 = 13, x1 = 1, x2 = 4, x3 = 1, and so on. We say an algorithm A represents a number x R+ if when given as input a nonnegative integer i, it returns the integer xi. For example, if A represents 10 + , then A(0) returns 13, A(1) returns 1, A(2) returns 4, and so on.
Recall that a number x is rational if can be expressed as a ratio a/b, where both a and b are b integers. For instance, 1/3 and 1/7 are rational, but and e are irrational. It is well known, and easy 37 to prove, that the rational numbers are countable.
(a) [3 points]. It is well known that there is an algorithm for representing each of our previous examples 1/3, 1/7, , and e. This is particularly noteworthy for and e, since these numbers are irrational. One might wonder if we could say the same thing for every number. Assuming the Church-Turing thesis, is there an algorithm for representing every nonnegative real number x R+? Prove your claim. You may use any facts mentioned in class or in the assigned readings as lemmas in your proof.
(b) [3 points]. Could you say the same thing about rational numbers, using the same argument you used in (a)? Why or why not?
Note that you do not need to provide a proof; just explain (briefly) whether or not the argument from (a) applies to rational numbers, and why.
(c) [9 points]. Suppose you are given an algorithm A, written in C++. You are also guaranteed that A represents some nonnegative real number x(A), but you don’t know which. In other words, you know the following for a fact about A:
When given a positive integer i as input, A eventually terminates and outputs a single-digit number xi(A) {0,1,...,9}
When given 0 as input, A eventually terminates and outputs a nonnegative integer x0(A).
You are asked to decide whether A represents a rational or irrational number. In other words, you must determine whether or not x(A) is rational, using only A’s C++ code as input. Assuming the Church-Turing thesis, show that this problem is undecidable.
Hints. You may use the following facts:
Given a Turing machine M, an input y, and an integer i, there is an algorithm for simulating M on y for i steps.
There is an algorithm which represents the number .
The number is irrational.