11,274 reputation
2860
bio website andrej.com
location Slovenia
age 43
visits member for 4 years
seen 10 hours ago

I am a professional mathematician and theoretical computer scientist (what is the difference?) . My area of work is a mix of logic, semantics, programming languages, category theory, constructive mathematics and computability.


2d
comment What is necessary and/or sufficient requirement for a subring of a field to be computable?
In these sorts of questions I find that the OP often does not really know what it means for a structure to be computable (present company excluded, of course). I think part of the problem is that people know too little about computability on mathematical structure to be even able to ask the question. For instance, this question seems to ask what might be some algebraic conditions on a ring to make it computable. The answer is: without further restrictions (such as "equality must be decidable") every ring can be equipped with a computable structure, albeit the trivial one.
Aug
29
awarded  Nice Answer
Aug
29
revised What is necessary and/or sufficient requirement for a subring of a field to be computable?
added 294 characters in body
Aug
29
comment What is necessary and/or sufficient requirement for a subring of a field to be computable?
Specifically, three people think that this question deserves closing because it is "too broad". But it is not. It is very specific, except that most people won't know how to formulate the concepts involved, in particular it would be helpful to explain what a "computable" ring is.
Aug
29
comment What is necessary and/or sufficient requirement for a subring of a field to be computable?
No need to close, this could go to Mathoverflow or here.
Aug
29
answered What is necessary and/or sufficient requirement for a subring of a field to be computable?
Aug
28
awarded  Yearling
Aug
15
awarded  Enlightened
Aug
14
awarded  Nice Answer
Aug
13
comment To what extent can the mathematics of Reals be applied to Computable Reals?
@Kaveh: yeah, we could wish for better terminology...
Aug
13
comment To what extent can the mathematics of Reals be applied to Computable Reals?
@Yakk: Bishop's definition of reals never mentions any "computability". He may talk about it in the accompanying text, but the definition is "just math": real is represented by a sequence $(a_n)_n$ of rational numbers such that $|a_n - a_m| < 1/n + 1/m$ for all $n, m$. The word "computable" does not appear, nor is it implied.
Aug
13
comment To what extent can the mathematics of Reals be applied to Computable Reals?
It's a bit of an oxymoron to say "true both constructively and classically". That's like saying I have "more than 50 and more than 30 euros in my pocket" -- remember that constructive implies classical.
Aug
12
comment To what extent can the mathematics of Reals be applied to Computable Reals?
I added a note to about the fact that intuitionistic logic is not the same thing as intuitionism. Also, the Wikipedia page on intuitionistic logic is awful.
Aug
12
revised To what extent can the mathematics of Reals be applied to Computable Reals?
added 161 characters in body
Aug
12
comment To what extent can the mathematics of Reals be applied to Computable Reals?
If you want $[0,1]$ to be Heine-Borel compact you should use Type Two Computability, i.e., the relative Kleene function realizability. There $[0,1]$ is computably Heine-Borel compact.
Aug
12
comment To what extent can the mathematics of Reals be applied to Computable Reals?
No, no, you need to distinguish between intuitionistic logic and Brower's intuitionism. Brouwer's intuitionism has extra axioms which imply that $[0,1]$ is Heine-Borel compact. Intutionistic logic is just classical logic without excluded middle (and no extra axioms), so it is compatible with classical logic. In intuitionistic logic we can show that $[0,1]$ is complete and totally bounded as a metric space, which is another kind of compactness. But we cannot show intuitionistically that $[0,1]$ is Heine-Borel compact.
Aug
12
answered To what extent can the mathematics of Reals be applied to Computable Reals?
Aug
11
awarded  Good Answer
Aug
6
awarded  Enlightened
Aug
6
awarded  Nice Answer