Funcția McCarthy 91
Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . |
În matematică discretă , Funcția lui McCarthy 91 este o funcție recursivă care returnează 91 pentru toate argumentele n ≤ 101 și returnează pentru . Limitat la setul de numere întregi mai mici de 102, prin urmare, este o funcție finală având un singur punct fix . Această funcție a fost concepută de informaticianul John McCarthy .
Funcția McCarthy 91 este definită după cum urmează:
Exemple:
M (99) = M (M (110)) deoarece 99 ≤ 100
= M (100) din moment ce 110> 100
= M (M (111)) deoarece 100 ≤ 100
= M (101) din moment ce 111> 100
= 91 din 101> 100
M (87) = M (M (98))
= M (M (M (109)))
= M (M (99))
= M (M (M (110)))
= M (M (100))
= M (M (M (111)))
= M (M (101))
= M (91)
= M (M (102))
= M (92)
= M (M (103))
= M (93)
.... continuă
= M (99)
(ca mai sus)
= 91
Poate că John McCarthy a scris funcția în acest fel, în limbajul de programare Lisp pe care el la inventat el însuși:
(defun mc91 (n)
(cond ((<= n 100) (mc91 (mc91 (+ n 11))))
(t (- n 10))))
Demonstrarea comportamentului descris al funcției urmează: Pentru 90 ≤ n <101,
M (n) = M (M (n + 11))
= M (n + 11 - 10), deoarece n> = 90 deci n + 11> = 101
= M (n + 1)
În consecință, M ( n ) = 91 ori 90 ≤ n <101.
Putem folosi acest rezultat ca caz de bază pentru inducerea pe 11 numere, astfel:
Să presupunem că M ( n ) = 91 pentru a ≤ n < a + 11.
Apoi, pentru fiecare n astfel încât a - 11 ≤ n < a ,
M (n) = M (M (n + 11))
= M (91), prin ipoteză, dat fiind că a ≤ n + 11 <a + 11
= 91, pentru cazul de bază.
Acum, prin inducție M ( n ) = 91 pentru fiecare n din acest bloc. Blocurile astfel considerate sunt adiacente, fără spații între ele, deci M ( n ) = 91 pentru n <101. De asemenea, putem adăuga n = 101 ca un caz special.
