[FOM] recursive vs. computable (Toby Ord)

Martin Davis martin at eipye.com
Fri Feb 13 21:49:01 EST 2004

Toby Ord writes:

<Of course, this problem is just due to some
historical question-begging terminological choices. I would personally
use "computing non-recursive functions" which is by no means
oxymoronic. Indeed, when writing on the topic, I take great care to
refer to the mathematical notion of recursiveness by that name only. I
think it is unfortunate that there is a trend towards terminology that
conflates the two (such as the move from r.e. to c.e.) and which
similarly begs Church's Thesis or some physical version of it. I don't
really understand why this has happened, but it is important not to be
put off by the historically odd terminology.>

There is nothing novel in the use of "computable" as a synonym for 
"recursive". It was Turing's original term, is in the title of my book of 
1958, and is the title of many courses in computer science departments. 
Even adherents of the hypercomputation movement (and surely that's what it 
has become) implicitly accept this in their use of the prefix "hyper".

Of course the substantive question is quite independent of the terminology. 
But researchers like Copeland and Siegelmann don't contribute anything but 
obfuscation when their claims are based entirely on preposterous claims 
about Turing's intentions, or on hiding the non-computability (or 
non-recursiveness if that makes anyone feel better) produced in an implicit 
input to the device.


More information about the FOM mailing list