Reputation
1,612
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
6 21
Impact
~38k people reached

2d
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
Jun
18
answered Proof that an property is definable if and only if its axiomatiazable and its complement its axiomatizable
Jun
18
comment Proof that an property is definable if and only if its axiomatiazable and its complement its axiomatizable
It would be helpful to people here if you could write what you mean by "property", "definable" and "axiomatizable" (in your class).
Jun
18
comment What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?
@GerryMyerson You mean $2q_{2k}-1$, right? I came up with something similar, but I wanted something not ad-hoc.
Jun
17
revised What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?
deleted 18 characters in body
Jun
17
revised What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?
added 10 characters in body
Jun
16
revised What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?
edited title
Jun
16
asked What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?