{"id":33047,"date":"2025-07-16T04:51:34","date_gmt":"2025-07-16T02:51:34","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=33047"},"modified":"2025-07-18T23:02:55","modified_gmt":"2025-07-18T21:02:55","slug":"lalacre-castoro","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2025\/07\/16\/lalacre-castoro\/","title":{"rendered":"L’alacre castoro"},"content":{"rendered":"

Non so se avete mai visto il nome scritto in italiano – credo ci fosse nelle traduzioni dei giochi matematici di Martin Gardner – ma se avete un po’ di dimestichezza con l’informatica teorica dovreste sapere che cos’\u00e8 il Busy Beaver<\/a>. O meglio non dovreste essere sicuri di saperlo, perch\u00e9 ci sono due diverse definizioni. Quella originale, proposta da Tibor Rado come funzione Sigma, rappresenta il massimo numero di 1 che una macchina di Turing a n<\/i> stati con due simboli (0 e 1) che termina la sua computazione pu\u00f2 stampare. Rapido ripasso: una macchina di Turing \u00e8 composta da un nastro infinito, una testina che pu\u00f2 leggere un simbolo per volta, e un insieme di stati che sono il suo programma, perch\u00e9 dicono cosa pu\u00f2 fare (scrivere un simbolo, eventualmente cancellarlo anche se nel nostro caso si suppone che il nastro contenga infiniti 0, spostarsi a sinistra o a destra ed entrare in un nuovo stato). Ci sono macchine di Turing che non terminano mai la computazione: per esempio se partiamo con un nastro pieno di zeri e abbiamo lo stato “se trovi scritto 0, scrivi 1 e vai a destra” avremo un nastro che si riempir\u00e0 di 1 dal punto di partenza a destra verso l’infinito. Queste macchine non sono cos\u00ec interessanti, quindi per il Busy Beaver si richiede che la macchina termini l’elaborazione. La seconda definizione, indicata come BB(n<\/i>), non conta gli uni scritti ma il numero massimo di passi che una macchina di Turing con n<\/i> stati pu\u00f2 compiere prima di fermarsi: anche in questo caso si richiede che la macchina effettivamente si fermi. <\/p>\n

Possiamo trovare i primi valori di queste funzioni, come al solito, su OEIS. Per quanto riguarda la funzione Sigma, abbiamo<\/a> <\/p>\n

$$\\Sigma(1) = 1; \\Sigma(2) = 4; \\Sigma(3) = 6; \\Sigma(4) = 13; \\Sigma(5) = 4098.$$<\/p>\n

I primi valori di BB() sono invece i seguenti: <\/p>\n

$$ BB(1) = 1; BB(2) = 6; BB(3) = 21; BB(4) = 107; BB(5) = 47176870.$$<\/p>\n

Il valore di BB(5) \u00e8 stato congetturato nel 1990 e dimostrato nel 2024<\/a>: per verificarlo si sono dovute studiare 88664064 macchine di Turing e decidere se si fermano oppure no. La macchina “vincente” ha questa definizione:<\/p>\n

\r\n         0       1\r\nA       1RB \t1LC\r\nB \t1RC \t1RB\r\nC \t1RD \t0LE\r\nD \t1LA \t1LD\r\nE \t--- \t0LA\r\n<\/pre>\n
La tabella si legge in questo modo: la colonna di sinistra indica in che stato si trova la macchina, la colonna centrale cosa succede se c’\u00e8 scritto 0 sotto la testina e quella di destra cosa succede se c’\u00e8 scritto 1; le triplette di caratteri dicono cosa scrivere (0 oppure 1), se andare a destra (R) o sinistra (L), e infine in quale stato posizionarsi. Non \u00e8 mai possibile arrivare nello stato E e vedere uno 0, quindi quella casella \u00e8 vuota. <\/p>\n
E quali sono i valori successivi delle due successioni? Non solo non lo si sa ma non lo si potr\u00e0 nemmeno sapere. Nel caso di Σ, sappiamo che Σ(6) > 10^^15. La notazione con doppio cappello, indicata a volte con l’esponente a sinistra ( 15<\/sup>10 ), \u00e8 la tetrazione, la generalizzazione di moltiplicazione ed elevamento a potenza. Come 3×5 = 3+3+3+3+3 e 3^5 = 3×3×3×3×3×, 3^^5 = 3^(3^(3^(3^3)))). 10^^15 \u00e8 insomma un numero cos\u00ec grande che \u00e8 praticamente inconcepibile. Ma BB(6) \u00e8 molto, molto, molto pi\u00f9 grande: Scott Aaronson riporta<\/a> che BB(6) > 2^^^5, dove il triplo cappelletto indica la pentazione, cio\u00e8 il passo successivo alla tetrazione. Questo risultato surclassa il vecchio limite che era “solo” 10^^10000000. Quanto \u00e8 grande quel numero? Aaronson spiega che se avessimo 10^^10000000 granelli di sabbia potremmo riempire 10^^10000000 copie dell’universo osservabile. S\u00ec, lo stesso numero, tanto il valore \u00e8 cos\u00ec grande che non ci si accorge della differenza. Numeri oltre ogni comprensione umana, insomma!<\/p>\n","protected":false},"excerpt":{"rendered":"
Una funzione che cresce tanto, ma tanto davvero.<\/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-33047","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-8B1","jetpack-related-posts":[{"id":35567,"url":"https:\/\/xmau.com\/notiziole\/2026\/01\/20\/biliardi-come-macchine-di-turing\/","url_meta":{"origin":33047,"position":0},"title":"Biliardi come macchine di Turing","author":".mau.","date":"2026-01-20","format":false,"excerpt":"Possiamo costruire un sistema perfettamente determinisitico ma il cui risultato \u00e8 indecidibile","rel":"","context":"In "mate-light 2026"","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"Il biliardo di Turing","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2026\/01\/biliardo-300x168.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":6372,"url":"https:\/\/xmau.com\/notiziole\/2008\/09\/21\/stupidi_giochi\/","url_meta":{"origin":33047,"position":1},"title":"stupidi giochi di parole","author":".mau.","date":"2008-09-21","format":false,"excerpt":"Gioco di parole purtroppo intraducibile","rel":"","context":"In "curiosit\u00e0-2008"","block_context":{"text":"curiosit\u00e0-2008","link":"https:\/\/xmau.com\/notiziole\/category\/curiosita\/curiosita-2008\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":8909,"url":"https:\/\/xmau.com\/notiziole\/2012\/06\/22\/99_anni_e_365_g\/","url_meta":{"origin":33047,"position":2},"title":"99 anni e 365 giorni","author":".mau.","date":"2012-06-22","format":false,"excerpt":"Domani \u00e8 il centesimo anniversario della nascita di Alan Turing","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":11423,"url":"https:\/\/xmau.com\/notiziole\/2015\/05\/31\/possibile\/","url_meta":{"origin":33047,"position":3},"title":"Possibile?","author":".mau.","date":"2015-05-31","format":false,"excerpt":"non capisco tanto odio sul simbolo","rel":"","context":"In "politica"","block_context":{"text":"politica","link":"https:\/\/xmau.com\/notiziole\/category\/politica\/"},"img":{"alt_text":"[il simbolo di Possibile]","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2015\/05\/possibile.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":27018,"url":"https:\/\/xmau.com\/notiziole\/2023\/09\/23\/importanza-dei-simboli-in-matematica-libro\/","url_meta":{"origin":33047,"position":4},"title":"Importanza dei simboli in matematica (ebook)","author":".mau.","date":"2023-09-23","format":false,"excerpt":"minimo ma interessante","rel":"","context":"In "rec-2023"","block_context":{"text":"rec-2023","link":"https:\/\/xmau.com\/notiziole\/category\/recensioni\/rec-2023\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/08\/9791220819862.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":3103,"url":"https:\/\/xmau.com\/notiziole\/2004\/09\/15\/storia_di_un_enigma\/","url_meta":{"origin":33047,"position":5},"title":"_Storia di un enigma_ (libro)","author":".mau.","date":"2004-09-15","format":false,"excerpt":"Una biografia forse troppo completa in certi punti e incompleta in altri.","rel":"","context":"In "rec-2004"","block_context":{"text":"rec-2004","link":"https:\/\/xmau.com\/notiziole\/category\/recensioni\/recensioni-2004\/"},"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\/33047","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=33047"}],"version-history":[{"count":7,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33047\/revisions"}],"predecessor-version":[{"id":33137,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/33047\/revisions\/33137"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=33047"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=33047"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=33047"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}