{"id":2513,"date":"2012-06-23T16:37:40","date_gmt":"2012-06-23T14:37:40","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2513"},"modified":"2022-10-11T10:57:07","modified_gmt":"2022-10-11T08:57:07","slug":"google-e-turing","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2012\/06\/23\/google-e-turing\/","title":{"rendered":"Google e Turing"},"content":{"rendered":"

Io ho una teoria. La percezione di Google da parte della gente \u00e8 migliore di quella di Microsoft per un’unica ragione: i doodle, i disegnini – ma non solo – che ogni poco compaiono nel motore di ricerca al posto dell’usuale scritta “Google”. Soprattutto da quando ogni tanto sono stati aggiunti quelli dinamici – a me cos\u00ec al volo viene in mente quello per Pac-Man<\/a>, il ricordo di John Lennon<\/a> e quello di Stanislaw Lem<\/a> – sono in molti a pensare “gente che perde tempo a preparare cose come queste deve essere fondamentalmente buona”. Ah, il marketing…<\/p>\n

Beh, oggi ricorre il centesimo anniversario della nascita di Alan Matheson Turing (ne avevo parlato ieri sul mio blog<\/a>, ma anche qui sul Post<\/a> potete trovare un articolo su di lui) e i googlisti hanno pensato di inserire una (finta) macchina di Turing<\/a> in suo ricordo! Quando oggi si apre la home page del motore di ricerca, si vede un nastro che si muove su e gi\u00f9, mentre si scrivono e cancellano numeri 0 e 1 per comporre i successivi numeri binari. Ma naturalmente la parte pi\u00f9 divertente inizia quando si clicca sul triangolino “play” e ci vengono presentati i quizzini da risolvere… Se vi siete persi e vi interessa solo la soluzione, potete guardare per esempio questo video<\/a>, oppure leggete qui<\/a>; se invece siete pi\u00f9 interessati alla logica dietro le macchine di Turing, continuate pure a leggere.<\/p>\n

\"Una<\/a>
\nPrima di tutto una notizia che far\u00e0 saltare molti sulla sedia: la macchina di Turing non \u00e8<\/b> un computer. Questo per varie ragioni: innanzitutto perch\u00e9 quando venne definita i computer non esistevano ancora, ed \u00e8 stato un caso che l’architettura definitiva dei calcolatori fosse definita a partire da essa; e soprattutto perch\u00e9 vi voglio vedere, a trovare un computer con disponibilit\u00e0 di memoria infinita. Turing aveva creato la sua macchina per scopi assolutamente teorici, vale a dire cercare un modo in cui formalizzare lo studio del problema della terminazione: \u00e8 sempre possibile sempre possibile, dato un insieme di istruzioni formali (un algoritmo, diremmo oggi) e un dato input finito, stabilire se l’elaborazione delle istruzioni arriver\u00e0 a un termine oppure si continuer\u00e0 a lavorare all’infinito? La risposta \u00e8 no, e la macchina di Turing \u00e8 per l’appunto un modello<\/b> (non un computer!) che permette di simulare un qualunque tipo di algoritmo.<\/p>\n

La definizione di macchina di Turing \u00e8 una cosa molto sfuggente, per l’ottima ragione che ci sono vari tipi di macchina tutti equivalenti tra di loro; quello che conta \u00e8 che ci sia un nastro<\/strong> illimitato diviso in caselle, una testina<\/strong> che possa leggere, scrivere e cancellare il contenuto di una casella oltre che spostarsi a sinistra e a destra, un insieme finito di simboli<\/strong> che possono essere scritti sulle caselle (diciamo 0,1, e lo spazio ” “) e un insieme finito di stati<\/strong>, vale a dire di istruzioni che dicono cosa la testina far\u00e0 quando si trova in una casella, a seconda di cosa ci sia scritto sulla casella stessa. Uno stato \u00e8 lo stato finale<\/strong>, che termina la computazione. Tutto qua. La memoria? La puoi avere nel nastro (tanto \u00e8 infinito, spazio per salvare cose ce n’\u00e8…); i salti condizionati corrispondono a stati diversi sullo stessa casella, e cos\u00ec via.<\/p>\n

\"Altro<\/a>
\nGli amici di Google hanno per\u00f2 un po’ barato: tra gli stati che vedete disegnati nelle due righe sotto il nastro potete notare quelli standard (spostarsi a sinistra e a destra), la scrittura di 0 e 1, gli “if” (quelli col quadratino), ma anche un GOTO che far\u00e0 mettere le mani nei capelli ai puristi ma \u00e8 comunque esprimibile in termini di macchina di Turing. Che aggiungere? Beh, nonostante il nastro infinito la macchina di Turing \u00e8 davvero minimale, ed \u00e8 quello che la fa apprezzare a un matematico, e forse un po’ meno a un informatico. Se siete riusciti a risolvere senza aiuto sia i primi sei problemi che i successivi sei a cui potete accedere cliccando in alto a sinistra sul doodle statico dopo aver finito il primo round, avete sicuramente una mente analitica!<\/p>\n","protected":false},"excerpt":{"rendered":"

La macchina di Turing in versione Google doodle…<\/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":[],"class_list":["post-2513","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-Ex","jetpack-related-posts":[{"id":2646,"url":"https:\/\/xmau.com\/ilpost\/2013\/10\/14\/carnevale-della-matematica-66\/","url_meta":{"origin":2513,"position":0},"title":"Carnevale della matematica #66","author":".mau.","date":"14\/10\/2013","format":false,"excerpt":"La raccolta dei post di argomento matematico nell'ultimo mese","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"Carnevale della Matematica","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2010\/07\/20090928-carnevale_matematica.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1514,"url":"https:\/\/xmau.com\/ilpost\/2019\/07\/25\/formule-matematiche-incomprensibili\/","url_meta":{"origin":2513,"position":1},"title":"Formule matematiche incomprensibili","author":".mau.","date":"25\/07\/2019","format":false,"excerpt":"Fare divulgazione matematica \u00e8 difficile, ma se si sbaglia a scrivere le formule i poveri lettori rimangono solo sconcertati.","rel":"","context":"In \"errori\"","block_context":{"text":"errori","link":"https:\/\/xmau.com\/ilpost\/tag\/errori\/"},"img":{"alt_text":"\u221a12 (1 - 1\/3,3 + 1\/5,3\u00b2 +1\/7,3\u00b3 + ...)","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/07\/gregory-ita.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/07\/gregory-ita.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/07\/gregory-ita.png?resize=525%2C300 1.5x"},"classes":[]},{"id":404,"url":"https:\/\/xmau.com\/ilpost\/2010\/10\/08\/il-quinto-postulato-di-euclide\/","url_meta":{"origin":2513,"position":2},"title":"Il quinto postulato di Euclide","author":".mau.","date":"08\/10\/2010","format":false,"excerpt":"Quello delle geometrie non euclidee \u00e8 un tema che non pu\u00f2 mancare in un blog di divulgazione matematica; il difficile \u00e8 riuscire a dire qualcosa di diverso dal solito. Cominciamo a vedere la storia dei tentativi di dimostrazione.","rel":"","context":"In \"geometria\"","block_context":{"text":"geometria","link":"https:\/\/xmau.com\/ilpost\/tag\/geometria\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":524,"url":"https:\/\/xmau.com\/ilpost\/2015\/03\/03\/chi-non-si-vaccina-fa-ammalare-anche-te\/","url_meta":{"origin":2513,"position":3},"title":"Chi non si vaccina fa ammalare anche te","author":".mau.","date":"03\/03\/2015","format":false,"excerpt":"In teoria si potrebbe pensare che se qualcuno non si vaccina \u00e8 solo un suo problema: beh, non \u00e8 proprio cos\u00ec.","rel":"","context":"In \"combinatorica\"","block_context":{"text":"combinatorica","link":"https:\/\/xmau.com\/ilpost\/tag\/combinatorica\/"},"img":{"alt_text":"[immunit\u00e0 di gregge]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/03\/Community_Immunity.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2474,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/06\/parole-matematiche-monotono\/","url_meta":{"origin":2513,"position":4},"title":"Parole matematiche: monotono","author":".mau.","date":"06\/02\/2012","format":false,"excerpt":"Quando si inventano parole dando loro una patina di classicit\u00e0, e gli accenti contano","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":199,"url":"https:\/\/xmau.com\/ilpost\/2012\/11\/26\/il-paradosso-di-braess\/","url_meta":{"origin":2513,"position":5},"title":"Il paradosso di Braess","author":".mau.","date":"26\/11\/2012","format":false,"excerpt":"Aggiungere nuove connessioni a una rete in certi casi pu\u00f2 portare a peggiorare le sue prestazioni. Sembra incredibile, ma \u00e8 una conseguenza matematica dell'ipotesi che ognuno sia egoista.","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"[il paradosso di Braess]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=525%2C300 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2513","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=2513"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2513\/revisions"}],"predecessor-version":[{"id":2514,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2513\/revisions\/2514"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2513"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2513"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2513"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}