If ℳ is a nonstandard model of PA (Peano arithmetic), with ℕ identified with the standard subset of ℳ, we can define six sets of subsets of ℕ which might be called “non-standard computable in ℳ”, namely:
ⓐ those X⊆ℕ for which there is e∈ℳ such that ∀i∈ℕ. ℳ⊧(e•i)↓ and ∀i∈ℕ. (i∈X⇔ℳ⊧(e•i)=1),
ⓑ those X⊆ℕ for which there is e∈ℕ such that ∀i∈ℕ. ℳ⊧(e•i)↓ and ∀i∈ℕ. (i∈X⇔ℳ⊧(e•i)=1),
ⓑ those X⊆ℕ for which there is e∈ℕ such that ∀i∈ℕ. ℳ⊧(e•i)↓ and ∀i∈ℕ. (i∈X⇔ℳ⊧(e•i)=1),
ⓒ those X⊆ℕ for which there is e∈ℳ such that ∀i∈ℳ. ℳ⊧(e•i)↓ and ∀i∈ℕ. (i∈X⇔ℳ⊧(e•i)=1),
ⓓ those X⊆ℕ for which there is e∈ℕ such that ∀i∈ℳ. ℳ⊧(e•i)↓ and ∀i∈ℕ. (i∈X⇔ℳ⊧(e•i)=1),
ⓓ those X⊆ℕ for which there is e∈ℕ such that ∀i∈ℳ. ℳ⊧(e•i)↓ and ∀i∈ℕ. (i∈X⇔ℳ⊧(e•i)=1),
ⓔ those X⊆ℕ for which there is e∈ℳ such that ∀i∈ℳ. ℳ⊧(e•i)↓ and ∀i∈ℳ. (i∈X⇔ℳ⊧(e•i)=1),
ⓕ those X⊆ℕ for which there is e∈ℕ such that ∀i∈ℳ. ℳ⊧(e•i)↓ and ∀i∈ℳ. (i∈X⇔ℳ⊧(e•i)=1).
ⓕ those X⊆ℕ for which there is e∈ℕ such that ∀i∈ℳ. ℳ⊧(e•i)↓ and ∀i∈ℳ. (i∈X⇔ℳ⊧(e•i)=1).
What are the relations between all six? What can we say about them from the perspective of computability (e.g., what are their sets of Turing degrees like)? I think this is what the following MO question is asking, but I hope someone can clarify! mathoverflow.net/q/412667/17064
Update: I forgot to say, e•i means “the result of the e-th Turing machine applied to input i” and (e•i)↓ means the computation terminates.
Formally, (e•i)↓ means ∃x.T(e,i,x), and e•i=1 means ∃x.(T(e,i,x) ∧ U(x)=1) where T is Kleene's T predicate: en.wikipedia.org/wiki/Kleene%27…
Formally, (e•i)↓ means ∃x.T(e,i,x), and e•i=1 means ∃x.(T(e,i,x) ∧ U(x)=1) where T is Kleene's T predicate: en.wikipedia.org/wiki/Kleene%27…
And more importantly, @JDHamkins posted a very nice answer characterizing (more or less fully according to the variant) these six sets as well as another variation I had forgotten:
https://twitter.com/JDHamkins/status/1482735229118951427
• • •
Missing some Tweet in this thread? You can try to
force a refresh
