Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Even if you can not compute the result in a finite number of steps through the naive approach there could still be a better approach, let me call it shortcut, for determining the value that can be computed. E.g. the geometric series result is known (a/(1-r)) but not computable through evaluating the series itself. A problem is undecidable if you can prove that the shortcut can not exist, it is decidable if you know a shortcut exists (knowing the formula is not required), and potentially either decidable or undecidable if a proof in either direction is unknown.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: