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

You seem to be using the word “computability” to mean “computable by an abstract machine of Turing degree 0”, whereas I am using it in the broader sense of “computable by an abstract machine of specified type”. As I said, in that broader sense, computability is non-trivial for finite machines.

And that broader sense is very standard, you’ll find heaps of papers/etc containing variations of the phrase “computable by a Turing machine with an oracle”… but if that oracle is e.g. for the standard (Turing degree 0) halting problem, then that halting problem is computable by such a machine.

You were earlier claiming I wasn’t familiar with the definitions, but you are giving me the impression you aren’t familiar with “computable” as a relative term



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

Search: