{"id":33788,"date":"2025-09-24T18:32:18","date_gmt":"2025-09-24T16:32:18","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=33788"},"modified":"2025-09-25T21:47:56","modified_gmt":"2025-09-25T19:47:56","slug":"la-funzione-91-di-mccarthy","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2025\/09\/24\/la-funzione-91-di-mccarthy\/","title":{"rendered":"La Funzione 91 di McCarthy"},"content":{"rendered":"<p>No, il maccartismo non c&#8217;entra. Questo McCarthy (John) \u00e8 l&#8217;informatico che ha realizzato il Lisp, oltre che essere un pioniere dell&#8217;intelligenza artificiale. La &#8220;<a href=\"https:\/\/it.wikipedia.org\/wiki\/Funzione_91_di_McCarthy\">Funzione 91<\/a>&#8221; \u00e8 una funzione ricorsiva definita sugli interi in questo modo:<\/p>\n<p>$$ M(n) = \\left\\{\\begin{matrix} n &#8211; 10, &#038; \\mbox{se }n > 100\\mbox{ } \\\\ M(M(n+11)), &#038; \\mbox{se }n \\le 100\\mbox{ } \\end{matrix}\\right. $$<\/p>\n<p>Notate come la ricorsione non sia semplice, come per esempio nel caso del fattoriale che possiamo definire come $n! = n \\times (n-1)!$ (e naturalmente $0! = 1$, per avere un punto in cui termina la ricorsione). Qui invece dobbiamo applicare due volte la definizione della funzione. <\/p>\n<p>Chiaramente se $ n \\gt 100 $ non ci sono problemi a calcolare $M(n)$: basta togliere 10. Anche per $n = 100$ facciamo in fretta: $ M(100) = M(M(100+11)) = M(M(111)) = M(101) = 91$. Il bello arriva quando proviamo a calcolare il suo valore per i numeri minori di 100. Proviamo per esempio con $ n = 42$: preparatevi a un ottovolante.<\/p>\n<pre>\r\nM(42) = M(M(42+11)) = M(M(53))\r\n      = M(M(M(64))) \r\n      = M(M(M(M(75))))\r\n      = M(M(M(M(M(86)))))\r\n      = M(M(M(M(M(M(97))))))\r\n      = M(M(M(M(M(M(M(108)))))))\r\n      = M(M(M(M(M(M(98))))))\r\n      = M(M(M(M(M(M(M(109)))))))\r\n      = M(M(M(M(M(M(99))))))\r\n      = M(M(M(M(M(M(M(110)))))))\r\n      = M(M(M(M(M(M(100))))))\r\n      = M(M(M(M(M(91)))))) (l'abbiamo visto sopra...)\r\n      = M(M(M(M(M(M(102))))))\r\n      = M(M(M(M(M(92))))))\r\n      = M(M(M(M(M(M(103))))))\r\n      = M(M(M(M(M(93))))))\r\n      = M(M(M(M(M(M(104))))))\r\n      = M(M(M(M(M(94))))))\r\n      = M(M(M(M(M(M(105))))))\r\n      = M(M(M(M(M(95))))))\r\n      = M(M(M(M(M(M(106))))))\r\n      = M(M(M(M(M(96))))))\r\n      = M(M(M(M(M(M(107))))))\r\n      = M(M(M(M(M(97))))))\r\n      = M(M(M(M(M(M(108))))))\r\n<\/pre>\n<p>Toh. Avevamo gi\u00e0 trovato $M(M(M(M(M(M(M(108)))))))$ con un livello di parentesi in pi\u00f9. Saltando un po&#8217; di passaggi continuiamo con <\/p>\n<pre>\r\nM(42) =\r\n      ...\r\n      = M(M(M(M(M(M(M(108))))))) \r\n      ...\r\n      = M(M(M(M(M(M(108))))))\r\n      ...\r\n      = M(M(M(M(M(108)))))\r\n      ...\r\n      = M(M(M(M(108))))\r\n      ...\r\n      = M(M(M(108)))\r\n      ...\r\n      = M(M(108))\r\n      ...\r\n      = M(98)\r\n      = M(M(109))\r\n      = M(99)\r\n      = M(M(110))\r\n      = M(100)\r\n      = M(M(111))\r\n      = M(101)\r\n      = 91\r\n<\/pre>\n<p>\u00c8 facile dimostrare per induzione (partendo dalla undicina $90 \u2264 n \\le 101$ e scendendo man mano di 11 in 11) che applicare $M$ a un qualunque numero intero minore di 100 porta a 91 (capito il perch\u00e9 del suo nome?). In pratica, la nostra funzione se ne sta piatta da meno infinito a 101, e poi diventa lineare. Strana, no?<\/p>\n<p>Aggiungo solo che la funzione \u00e8 usata come test per verificare i programmi automatici di verifica del software, proprio per la sua struttura cos\u00ec strana.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Una funzione divertente da calcolare <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"federated","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1005,214],"tags":[],"class_list":["post-33788","post","type-post","status-publish","format-standard","hentry","category-matelight-2025","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-8MY","jetpack-related-posts":[{"id":20606,"url":"https:\/\/xmau.com\/notiziole\/2020\/07\/12\/quizzino-della-domenica-somme-di-potenze\/","url_meta":{"origin":33788,"position":0},"title":"Quizzino della domenica: somme di potenze","author":".mau.","date":"2020-07-12","format":false,"excerpt":"Dimostrate che ci sono infiniti quadrati della forma 2m + 2n, con m e n interi positivi distinti; dimostrate inoltre che ci sono infiniti quadrati della forma 3m + 3n, sempre con m e n interi positivi distinti. (un aiutino lo trovate sul mio sito, alla pagina http:\/\/xmau.com\/quizzini\/p460.html; la risposta\u2026","rel":"","context":"In &quot;giochi&quot;","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2020\/06\/q460a.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":34584,"url":"https:\/\/xmau.com\/notiziole\/2025\/12\/03\/come-dimostrare-che-e-e-irrazionale\/","url_meta":{"origin":33788,"position":1},"title":"Come dimostrare che e \u00e8 irrazionale","author":".mau.","date":"2025-12-03","format":false,"excerpt":"Una dimostrazione alla portata di uno studente liceale.","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":34230,"url":"https:\/\/xmau.com\/notiziole\/2025\/11\/05\/rsa-non-e-piu-quello-di-una-volta-ii\/","url_meta":{"origin":33788,"position":2},"title":"RSA non \u00e8 pi\u00f9 quello di una volta (II)","author":".mau.","date":"2025-11-05","format":false,"excerpt":"La phi di Eulero non \u00e8 davvero necessaria, anche se cambia in realt\u00e0 poco.","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7805,"url":"https:\/\/xmau.com\/notiziole\/2010\/04\/01\/ricorsione\/","url_meta":{"origin":33788,"position":3},"title":"Ricorsione","author":".mau.","date":"2010-04-01","format":false,"excerpt":"due parole sulla ricorsione, o come si pu\u00f2 definire una cosa per mezzo di s\u00e9 stessa.","rel":"","context":"In &quot;matematica_light&quot;","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":36233,"url":"https:\/\/xmau.com\/notiziole\/2026\/03\/11\/numeri-primoriali-e-compositoriali\/","url_meta":{"origin":33788,"position":4},"title":"Numeri primoriali e compositoriali","author":".mau.","date":"2026-03-11","format":false,"excerpt":"Perch\u00e9 i fattoriali sono troppo mainstream","rel":"","context":"In &quot;mate-light 2026&quot;","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7749,"url":"https:\/\/xmau.com\/notiziole\/2010\/03\/11\/fibonacci_e_lin\/","url_meta":{"origin":33788,"position":5},"title":"Fibonacci e l&#8217;induzione","author":".mau.","date":"2010-03-11","format":false,"excerpt":"un teorema sui numeri di Fibonacci dimostrabile con l'induzione","rel":"","context":"In &quot;matematica_light&quot;","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33788","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=33788"}],"version-history":[{"count":8,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33788\/revisions"}],"predecessor-version":[{"id":33808,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33788\/revisions\/33808"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=33788"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=33788"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=33788"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}