semialgoritmo

semialgoritmo

semialgoritmo procedura definita per risolvere un problema la quale termina in un numero finito di passi se il problema ha soluzione, mentre non ha termine se il problema non ha soluzione; è, quindi, semicalcolabile. Si consideri per esempio il seguente procedimento utilizzato per estrarre la radice quadrata aritmetica r di un numero intero positivo n:

1) si pone r uguale a 0;

2) si calcola il valore di r ², se r ² è uguale a n allora r è la radice quadrata di n altrimenti si va al passo successivo;

3) si incrementa r di una unità (r ≔ r + 1) e si ritorna al passo 2.

Se, per esempio, n = 9 si effettuano i seguenti passaggi: si pone r = 0; dato che 0² = 0 ≠ 9 si passa a r = 1; dato che 1² = 1 ≠ 9 si passa a r = 2; dato che 2² = 4 ≠ 9 si passa a r = 3; dato che 3² = 9 il procedimento termina con il calcolo della radice quadrata di 9 uguale a 3. Tuttavia, se si prova a calcolare, con la stessa procedura, la radice quadrata di 8, la procedura non termina, poiché 8 non è un quadrato perfetto. Come per un algoritmo, il procedimento di calcolo definito da un semialgoritmo si articola in una sequenza di operazioni non ambigue le quali devono poter essere eseguibili da un automa in modo deterministico, tale cioè che a ogni passo della procedura deve essere univocamente determinata l’operazione da eseguire; tuttavia, mentre un algoritmo è sempre una procedura finita, qualunque sia il dato in ingresso, in un semialgoritmo può accadere che un passaggio sia ripetuto infinite volte dando origine a un calcolo che non termina mai. La differenza fra algoritmo e semialgoritmo è strettamente collegata alla differenza fra → insieme decidibile e insieme semidecidibile.