For this question answer individual parts. (a) The McCarthy 91 function is defin
ID: 3916595 • Letter: F
Question
For this question answer individual parts. (a) The McCarthy 91 function is defined using the rule: M(n) = n ? 10 if n > 100 M(M(n + 11)) if n ? 100 By successively using the defining rule for M(n), find M(87) Answer:
(b) A set is well ordered if every nonempty subset of this set has a least element. Determine if the set of integers greater than -100 is well ordered. Answer:
(c) Find the flaw with the following ”proof” that every postage of three cents or more can be formed using just three-cent and four-cent stamps. Basis Step: We can form postage of three cents with a single three-cent stamp and we can form postage of four cents using a single four-cent stamp. Inductive Step: Assume that we can form postage of j cents for all nonnegative integers j with j ? k using just three-cent and four-cent stamps. We can then form postage of k + 1 cents by replacing one three-cent stamp with a four-cent stamp or by replacing two four-cent stamps with three three-cent stamps. Answer:
Explanation / Answer
Answer:
a) MaCarthy function is defined as:
M(n) = n-10 if n > 100 or
M(M(n+11) if n <= 100
for n = 87, we have:
M(n) = M(87)
= M(M(87+11)) as 87 <=100
= M(M(98))
= M(M(M(98+11))) as 98 <=100
= M(M(M(109)))
= M(M(109-10)) as 109>100
= M(M(99))
= M(M(M(99+11))) as 99 <= 110
= M(M(M(110)))
= M(M(110-10)) as 110 > 100
= M(M(100))
= M(M(M(110+11))) as 100 <= 100
= M(M(M(111)))
= M(M(111-10)) as 111 > 100
= M(M(101))
= M(101-10) as 101 > 100
= M(91)
= M(M(91 + 11)) as 91 <= 100
= M(102)
= M(102-10) as 102 > 100
= M(92)
= M(M(92+11)) as 92 <= 100
= M(M(103))
= M(103 - 10) as 103 > 100
= M(93)
= M(M(93+11)) as 93 <= 100
= M(104)
= M(104 - 10) as 104 > 100
= M(94)
= M(M(94+11)) as 94 <= 100
= M(M(105))
= M(105 - 10) as 105 > 100
= M(95)
= M(M(95 + 11)) as 95 <= 100
= M(M(106))
= M(106 - 10) as 106 > 100
= M(96)
= M(M(96 + 11)) as 96 <= 100
= M(M(107))
= M(107-10) as 107 > 100
= M(97)
= M(M(97+11)) as 97 <= 100
= M(M(108))
= M(108-10) as 108 > 100
= M(98)
= M(M(98+11)) as 98 <= 100
= M(M(109))
= M(109 - 10) as 109 > 100
= M(99)
= M(M(99 + 11)) as 99 <= 100
= M(M(110))
= M(110-10) as 110 > 100
= M(100)
= M(M(100+11)) as 100 <= 100
= M(M(111))
= M(111-10) as 111 > 100
= M(101)
= 101 - 10 as 101 > 100
= 91
b) A set of integers greater than -100 will have positive as well as negative integers. Well-ordering property is the property of positive integers. Hence such a set will not be well-ordered.
c) The flaw is with induction step. It is assumed for j > k, while it should be assumed to be true for some integer k.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.