5
$\begingroup$

Is there a natural, non-trivial example of a TCA (total combinatory algebra, cf. pca) with a natural notion of an oracle?

$\endgroup$
4
  • $\begingroup$ Bob, could you provide a little more background on TCA's, or a link where we can find out more? Is this post relevant: mathoverflow.net/a/57489/1946? $\endgroup$ – Joel David Hamkins Dec 9 '14 at 1:36
  • $\begingroup$ A reference on TCAs: janwillemklop.nl/Jan_Willem_Klop/Bibliography_files/… $\endgroup$ – Joel David Hamkins Dec 9 '14 at 2:56
  • $\begingroup$ Joel, those are some great references. I don't know of any standard reference. Pca's are used in realizability, so any reference work including realizability would have to talk about them. They're in Beeson's book, and likely van Oosten's "Realizability." I'd think they'd be in any good book on the lambda-calculus too. $\endgroup$ – Robert Lubarsky Dec 9 '14 at 17:00
  • $\begingroup$ I'm surprised that Andrej's suggestion of just defining "divergence" as 42 (with the Turing functions, K_1) actually works. So that's not a bad example, but noticeably unnatural, even if just in that one spot. $\endgroup$ – Robert Lubarsky Dec 9 '14 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.