Reputation
1,637
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
6 22
Impact
~40k people reached

Aug
24
awarded  Popular Question
Aug
23
revised Injury-free proof of Cof being $\Sigma^0_3$-complete
added 118 characters in body
Aug
23
revised Injury-free proof of Cof being $\Sigma^0_3$-complete
edited body; edited title
Aug
23
asked Injury-free proof of Cof being $\Sigma^0_3$-complete
Aug
3
comment Model-theoretic characterization of local modal correspondence
I believe I figured this out and might write the solution down later.
Aug
3
revised Model-theoretic characterization of local modal correspondence
added 50 characters in body
Aug
3
asked Model-theoretic characterization of local modal correspondence
Jul
26
revised Reference request: fixed point and first-order logics
added 164 characters in body
Jul
25
asked Reference request: fixed point and first-order logics
Jul
2
comment Primitive recursion and $\Delta^0_0$
@QuinnCulver That's exactly why I confused the two; some describe primitive recursive functions as "only for-loops, not while-loops", including a Wikipedia article en.wikipedia.org/w/… and a book I skimmed a few years ago (too bad I don't have the copy and the book isn't in English). There should be a subtle technical point which I should have missed, I think.
Jun
27
comment What does “Turing-complete” really mean?
@AsafKaragila I myself do not think that my question might well be moved. My question is also applicable to coding schema of partial computable functions that are not of interest in theory of programming languages - like codes of Turing machines. Also pathologies I mentioned like m-complete non-T-complete sets are more about abstract computability and logic, I think. I can't deny the possibility of interesting answers coming out from theoretical computer scientists, though.
Jun
24
revised What does “Turing-complete” really mean?
added 91 characters in body
Jun
24
revised What does “Turing-complete” really mean?
deleted 48 characters in body
Jun
24
comment What does “Turing-complete” really mean?
@James For T-degree, I am only thinking of r.e. sets (I've updated the statement to make this clear.) For m-degree, isn't it just true that every complete set is the halting set for some encoding, since they are all recursively isomorphic? (I'm reasoning sloppy.)
Jun
24
revised What does “Turing-complete” really mean?
added 6 characters in body
Jun
24
comment What does “Turing-complete” really mean?
@James Is it equivalent to $K_L \equiv_T 0'$, $K_L \equiv_m 0'$ or neither? (I know there's some sloppiness in what I wrote since partial functions should be single-valued)
Jun
24
revised What does “Turing-complete” really mean?
added 11 characters in body
Jun
24
asked What does “Turing-complete” really mean?
Jun
21
asked Primitive recursion and $\Delta^0_0$
Jun
18
revised Proof that an property is definable if and only if its axiomatiazable and its complement its axiomatizable
added 3 characters in body