Si supponga di avere due insiemi A, B<\/i>, supposti infiniti enumerabili,
\n ovvero che si ipotizzino aventi la stessa cardinalit\u00e0 <\/i>dei
\n numeri naturali, e sia f(n)<\/i> una corrispondenza biunivoca tale che
\n B=f(A)<\/i>.<\/p>\n
Si disponga, inoltre, delle propriet\u00e0 PA(n)<\/i> e PB(n)<\/i>
\n occorrenti alla definizione degli elementi in A<\/i> e B<\/i>.<\/p>\n
Ad esempio:<\/p>\n
A = l’insieme dei numeri naturali dispari<\/i><\/p>\n<\/li>\n B = l’insieme dei numeri naturali pari<\/i><\/p>\n<\/li>\n PA(n) = n \u00e8 dispari se n\/2 ha resto 1<\/i><\/p>\n<\/li>\n PB(n) = n \u00e8 pari se n\/2 ha resto 0<\/i><\/p>\n<\/li>\n<\/ul>\n e si supponga di voler testare se la mappa<\/p>\n f(n)=n+1<\/i><\/p>\n tra i numeri naturali pari e quelli dispari sia biunivoca.<\/p>\n La dimostrazione “computazionale” di una corrispondenza biunivoca Per l’esecuzione dell’algoritmo non sono necessarie due macchine di Turing; Una funzione \u00e8 detta computabile<\/i> se esiste un algoritmo \n <\/p>\n sia n=0;<\/i><\/p>\n ripeti <\/i> <\/p>\n aumenta n di 1;<\/i><\/p>\n aumenta n di 1;<\/i><\/p>\n finch\u00e8 PB(f(n))<\/i> \u00e8 FALSA;<\/p>\n \n <\/p>\n l’algoritmo termina quando la mappa f <\/i>, supposta corrispondenza Viceversa, l’algoritmo non termina se la propriet\u00e0 \u00e8 verificata. In linea teorica avremmo a disposizione un algoritmo che computi la enumerabilit\u00e0 Uno strumento pi\u00f9 maneggevole, per noi umani, per la dimostrazione Sia P(n) <\/i>una propriet\u00e0 ed A <\/i>un insieme infinito se <\/p>\n \n P(n)<\/i> \u00e8 VERA per il primo elemento di A <\/i>(passo e<\/p>\n \n supposto che P(n) <\/i>\u00e8 VERA implichi che P(SUCC(n))<\/i> allora<\/p>\n P(n) <\/i>\u00e8 VERA per tutti gli elementi di A<\/i><\/p>\n \n <\/p>\n ove SUCC(n)<\/i> sia una qualsiasi funzione primitiva che determini Una branca interessantissima della Scienza dei Calcolatori, la Dimostrazione […]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[72],"tags":[],"class_list":["post-2190","post","type-post","status-publish","format-standard","hentry","category-teoria-dei-numeri"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2190","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=2190"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2190\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=2190"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=2190"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=2190"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n \u00e8, in linea teorica applicabile, ovvero esiste un’algoritmo che
\n dimostra la corrispondenza biunivoca tra A <\/i>e B<\/i>.<\/p>\n
\n posto un’ordinamento completo di A<\/i> e B<\/i>, una sola Macchina
\n di Turing pu\u00f2 testare, ad ogni passo, se per ogni n <\/i>dispari,
\n i.e. per cui PA(n)<\/i> \u00e8 vera, allora PB(f(n))<\/i> \u00e8
\n vera.<\/p>\n
\n che la calcola; f<\/i> \u00e8 computabile e l’algoritmo che la calcola
\n \u00e8 il seguente:<\/p>\n
\n biunivoca fallisce di verificare la propriet\u00e0 PB(n).<\/i><\/p>\n
\n Possiamo quindi affermare che la mappa f(n) \u00e8 una corrispondenza
\n biunivoca se l’algoritmo non termina<\/i>.<\/p>\n
\n degli insiemi infiniti. Peccato che, per i limiti intrinseci di noi umani,
\n non potremmo sopravvivere per vederne il risultato.<\/p>\n
\n di propriet\u00e0 su insiemi infiniti enumerabili \u00e8 il principio
\n di induzione.<\/i><\/p>\n
\n enumerabile:<\/p>\n
\n base dell’induzione<\/i>)<\/p>\n
\n sia vera (ipotesi induttiva<\/i>)<\/p>\n
\n il successore dell’n-mo elemento di A<\/i>.<\/p>\n
\n Automatica dei Teoremi<\/i>, consente, con i suoi risultati, di ideare
\n algoritmi che siano in grado di dimostrare teoremi in generale, purch\u00e8
\n posti in una forma data. Fortunatamente, il principio di induzione per
\n una propriet\u00e0 P(n)<\/i> ed un insieme infinito enumerabile A<\/i>
\n rientra tra i teoremi dimostrabili e, quindi, una dimostrazione di biunivocit\u00e0
\n pu\u00f2 essere determinata proprio applicando questi risultati ad una
\n Macchina di Turing, piuttosto che “per forza bruta”.<\/p>\n","protected":false},"excerpt":{"rendered":"