حدس کنوث (Knuth’s Conjecture)

دانشمند معروف علوم کامپیوتر آمریکایی، دونالد کنوث (Donald Knuth)، حدسی را مطرح کرده است که بر اساس آن می‌توان با عدد 3 شروع کرد و با به‌کارگیری ترکیبی از توابع فاکتوریل، ریشه‌ی دوم و جزء صحیح، هر عدد طبیعی دلخواه را به دست آورد. این توابع را به صورت توابع تودرتو با ورودی 3 به کار می‌بریم. هر کدام از این توابع را می‌توان چند بار به کار برد. خروجی نهایی یک عدد صحیح است.

 برای مثال، اگر می‌خواهیم از عدد 3 به عدد 26 برسیم، نخست تابع فاکتوریل را بر عدد 3 اعمال می‌کنیم و !3 را که برابر با 6 است به دست می‌آوریم. سپس تابع فاکتوریل را برای عدد 6  به کار می‌گیریم که خروجی آن !6 یا 720 است. آن‌گاه ریشه‌ی دوم 720 را محاسبه می‌کنیم که تقریباً برابر است با 26/83 . جزء صحیح این عدد، عدد موردنظر یعنی 26 است.

floor(sqrt((3!)!))

   = floor(sqrt(6!))

   = floor(sqrt(720))

   = floor(26.83...)

   = 26

اگر در مثال بالا سه بار پی‌درپی تابع ریشه‌ی دوم را به کار بگیریم، به عدد 5 می‌رسیم:

floor(sqrt((3!)!))

   = floor(sqrt(6!))

   = floor(sqrt(720))

   = floor(sqrt(26.83...))

   = floor(5.18...)

   = 5

بعدها درستی حدس کنوث توسط ریاضیدانان به اثبات رسید. با جستجویی در اینترنت می‌توانید شیوه‌ی اثبات آن را بیابید. حدس کنوث را می‌توان به عنوان تمرینی در زمینه‌ی هوش مصنوعی مطرح کرد که در آن وضعیت اولیه عدد 3 است و هدف رسیدن به یک عدد طبیعی دلخواه است. با استفاده از یک الگوریتم جستجوی مناسب می‌توان عامل هوشمند را قادر ساخت تا مسیر درست و بهینه را به ما نشان دهد.