Hesaplanabilir fonksiyon

Bir hesaplanabilir fonksiyonu (veya yinelemeli fonksiyonu ) a, yarı hesaplanabilir fonksiyonu (veya yinelemeli kısmi işlevi de) toplam , tüm alanı üzerinde tanımlanmıştır ve özellikle de,. Bunlar, "sonlandırıcı" bir Turing makinesi tarafından hesaplanan işlevlerdir .

Hesaplanabilir bir işlev, örneğin uygulama süresi birkaç milyar yılı aşıyorsa, mutlaka “fiziksel olarak hesaplanabilir” değildir.

Hesaplanabilir fonksiyonların en basit örnekleri sabit fonksiyonlardır . Dışarıda bırakılan üçüncü ilkenin bir sonucu, Goldbach varsayımı doğruysa 1'i ve yanlışsa 0'ı bir tamsayı ile ilişkilendiren sabit fonksiyonun hesaplanabilir olmasıdır, ancak bugün varsayımın doğru olup olmadığını bilmiyoruz. Bu, bu ilkenin uygulanmasının herhangi bir sezgisel hesaplanabilirlik kavramını nasıl yok ettiğini gösterir.

Örnekler

• Durduran bilgisayar programları (herhangi bir girişte yürütülürken) hesaplanabilir işlevlerdir.

• Girdi olarak bir Turing makinesini (bir tamsayı ile temsil edilir) ve bu makine için bir girdi alan ve bu makine bu girdide durursa bunları 1 ile ilişkilendiren işlev, başka türlü bir şey değil, yarı hesaplanabilir bir işlevdir. Yalnızca hariç tutulan üçüncü ilkenin bir uygulaması, bu işlevi, dikkate alınan makine dikkate alınan girdi üzerinde durmazsa 0 veren bir toplam işleve genişletmeyi mümkün kılar, ancak bu işlev bu durumda hesaplanamaz (bilgiden fazlası için bkz. makale Kapatma sorunu ).
• Bir hesaplama GCD'nın hesaplanabilir fonksiyonudur.

Referanslar

1. Alain Prochiantz , Makine-Zihin , Odile Jacob,5 Ocak 2001( çevrimiçi okuyun ).

Ayrıca görün

• Kilise tezi
• Hesaplanabilirlik
• Karar Verilebilirlik