b'\n_START_ARTICLE_\nTeorema dello speedup di Blum\n_START_PARAGRAPH_\nNella teoria della complessit\xc3\xa0 computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, \xc3\xa8 un importante teorema dello speedup riguardante la complessit\xc3\xa0 delle funzioni calcolabili._NEWLINE_Ogni funzione calcolabile ha un infinito numero di differenti rappresentazioni in un dato linguaggio di programmazione. Nella teoria della computabilit\xc3\xa0 si ha spesso la necessit\xc3\xa0 di trovare un algoritmo di minor complessit\xc3\xa0 per una data funzione calcolabile e una data classe di complessit\xc3\xa0._NEWLINE_Il teorema dello speedup di Blum sostiene che per ogni classe di complessit\xc3\xa0 esistono funzioni calcolabili per la cui elaborazione non esistono programmi pi\xc3\xb9 efficienti (veloci).\n_START_SECTION_\nDefinizione\n_START_PARAGRAPH_\nData una funzione totale (ricorsiva)  (a due parametri), allora esiste una funzione totale  (booleana, ossia con ) (o equivalentemente predicato ricorsivo) tale che per ogni programma (algoritmo)  per , esiste un programma  per , tale che per quasi tutti gli  si verifica che_NEWLINE_La funzione  \xc3\xa8 detta funzione speedup._NEWLINE_Semplificando, esistono svariati algoritmi per i quali non esiste un algoritmo pi\xc3\xb9 veloce, in quanto per ogni macchina di Turing che implementa il programma , ne esiste sempre una (che implementa ) pi\xc3\xb9 prestante.'