{"id":888,"date":"2016-09-07T04:04:49","date_gmt":"2016-09-07T03:04:49","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=888"},"modified":"2016-09-06T10:14:52","modified_gmt":"2016-09-06T09:14:52","slug":"life-e-i-numeri-primi-pillole","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2016\/09\/07\/life-e-i-numeri-primi-pillole\/","title":{"rendered":"Life e i numeri primi [Pillole]"},"content":{"rendered":"<p>Sicuramente conoscete <a href=\"https:\/\/it.wikipedia.org\/wiki\/Gioco_della_vita\">Life<\/a> di Conway. Forse avete anche sentito dire che \u00e8 stato dimostrato che \u00e8 equivalente a una macchina di Turing: detto in altro modo, qualunque tipo di computazione che possiamo fare con un qualunque computer pu\u00f2 essere simulato da una opportuna configurazione iniziale di Life. Il risultato \u00e8 teorico, il che significa che nessuno si preoccupa della velocit\u00e0 di esecuzione, ma soprattutto che nessuno si mette ad esplicitare quale configurazione corrisponde al nostro calcolatore di Conway.<\/p>\n<p><span class=\"embed-youtube\" style=\"text-align:center; display: block;\"><iframe loading=\"lazy\" class=\"youtube-player\" width=\"640\" height=\"360\" src=\"https:\/\/www.youtube.com\/embed\/68nEX5CEmZE?version=3&#038;rel=1&#038;showsearch=0&#038;showinfo=1&#038;iv_load_policy=1&#038;fs=1&#038;hl=en-US&#038;autohide=2&#038;wmode=transparent\" allowfullscreen=\"true\" style=\"border:0;\" sandbox=\"allow-scripts allow-same-origin allow-popups allow-presentation allow-popups-to-escape-sandbox\"><\/iframe><\/span><\/p>\n<p>Quasi nessuno, per la precisione. Dean Hickerson progett\u00f2 nel 1991 <a href=\"http:\/\/www.nathanieljohnston.com\/2009\/08\/generating-sequences-of-primes-in-conways-game-of-life\/\">un generatore di numeri primi<\/a>. Come potete vedere nel video qui sopra, le 2953 celle della configurazione di partenza emettono alla generazione 120<i>N<\/i>+100 una &#8220;astronave leggera&#8221; (il nome di una configurazione in Life) per alcuni specifici valori di <i>N<\/i>: tutti e soli i numeri primi (diversi da 2 e 3). Esistono anche alcune versioni modificate: la pi\u00f9 divertente \u00e8 a mio parere quella che genera tutti e soli i primi di Fermat :-)<\/p>\n<p>Come pu\u00f2 funzionare una cosa del genere? Come fa l&#8217;automa cellulare di Life a creare una successione a prima vista impredicibile come quella dei numeri primi? Il trucco \u00e8 che applica il crivello di Eratostene, che \u00e8 un algoritmo perfettamente definito. Se guardate il video, notate delle righe diagonali di astronavi in alto a destra: corrispondono per l&#8217;appunto ai numeri primi generati, che cancellano le astronavi relative ai loro multipli. Semplice a vedersi, un po&#8217; meno a crearsi! <\/p>\n<p>(H\/T: <a href=\"http:\/\/mathtango.blogspot.com\/2016\/08\/some-end-of-week-picks.html\">Math Tango<\/a>)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esiste una configurazione di Life che genera i numeri primi<\/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":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","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":[1],"tags":[159,158,78],"class_list":["post-888","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-conway","tag-life","tag-numeri-primi"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-ek","jetpack-related-posts":[{"id":672,"url":"https:\/\/xmau.com\/ilpost\/2015\/12\/03\/teoremi-e-probabilita\/","url_meta":{"origin":888,"position":0},"title":"Teoremi e probabilit\u00e0","author":".mau.","date":"03\/12\/2015","format":false,"excerpt":"Sembrano due concetti agli antipodi, eppure si possono dimostrare alcuni teoremi con metodi probabilistici.","rel":"","context":"In \"dimostrazioni\"","block_context":{"text":"dimostrazioni","link":"https:\/\/xmau.com\/ilpost\/tag\/dimostrazioni\/"},"img":{"alt_text":"cerchi","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/12\/cerchi-300x182.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":1441,"url":"https:\/\/xmau.com\/ilpost\/2019\/03\/07\/la-dimostrazione-matematica-piu-lunga\/","url_meta":{"origin":888,"position":1},"title":"La dimostrazione matematica pi\u00f9 lunga","author":".mau.","date":"07\/03\/2019","format":false,"excerpt":"\u00c8 impossibile che qualche essere umano la possa leggere.","rel":"","context":"In \"combinatoria\"","block_context":{"text":"combinatoria","link":"https:\/\/xmau.com\/ilpost\/tag\/combinatoria\/"},"img":{"alt_text":"un esagono colorato di rosso e blu","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/03\/esagono-300x248.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2584,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/03\/euclide-aritmetico\/","url_meta":{"origin":888,"position":2},"title":"Euclide aritmetico","author":".mau.","date":"03\/04\/2013","format":false,"excerpt":"Gli Elementi non parlano solo di geometria, ma anche di aritmetica; e anche qua brilla l'esposizione di Euclide.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/04\/Euclids_algorithm_Book_VII_Proposition_2_3.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":460,"url":"https:\/\/xmau.com\/ilpost\/2013\/02\/06\/mersenne-48\/","url_meta":{"origin":888,"position":3},"title":"Mersenne 48","author":".mau.","date":"06\/02\/2013","format":false,"excerpt":"\u00c8 stato scoperto un nuovo numero primo di Mersenne, o se preferite un nuovo numero perfetto.","rel":"","context":"In \"attualit\u00e0\"","block_context":{"text":"attualit\u00e0","link":"https:\/\/xmau.com\/ilpost\/tag\/attualita\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2626,"url":"https:\/\/xmau.com\/ilpost\/2013\/07\/12\/epidemie\/","url_meta":{"origin":888,"position":4},"title":"Epidemie","author":".mau.","date":"12\/07\/2013","format":false,"excerpt":"Un problema matematico la cui dimostrazione \u00e8 un'applicazione del concetto di monovariante.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2598,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/26\/parilandia\/","url_meta":{"origin":888,"position":5},"title":"Parilandia","author":".mau.","date":"26\/04\/2013","format":false,"excerpt":"Noi diamo per scontata la fattorizzazione unica, ma non \u00e8 sempre cos\u00ec.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/888","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=888"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/888\/revisions"}],"predecessor-version":[{"id":889,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/888\/revisions\/889"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}