Chris Pressey
|
Registered User
|
My main interest is in the design of pathological programming languages. While this subject is not entirely (perhaps not even primarily) mathematical, it does rely significantly on results from computability, complexity theory, and formal languages. Results from pretty much any field are welcome additions if they can be applied to the design of a programming language to make it (more) pathological. Currently I am somewhat interested in the possibilities of abstract algebra in this regard.
|
|
Dec 3 |
answered | Can infinity shorten proofs a lot? |
|
Dec 2 |
comment |
If NP=EXPTIME, does every DTM have a succinct “execution proof”? Thank you. I doubt that these hypothetical polylogarithmic execution proofs could be useful for much, but as computational oddities, I find them pleasing, and it's nice to know I wasn't just deluding myself into this conclusion. (It's also sobering to be reminded how much I've forgotten about the primitive recursive functions!) |
|
Dec 1 |
comment |
Examples of common false beliefs in mathematics. A somewhat glib "constructivist" argument that might work on some people: Suppose I have a number 0.999...; you say it is not 1, so what would you have to add to my 0.999... to make it 1? When they say 0.000..., point out that if I never stop adding 9-digits to my number, then they can't stop adding 0-digits to theirs, so surely theirs is 0, and mine is 1. |
|
Nov 29 |
comment |
Between mu- and primitive recursion This question appears to be very closely related: mathoverflow.net/questions/35461/… |
|
Nov 29 |
comment |
Interesting complexity classes $PR \subsetneq c \subsetneq R$ This question appears to be very closely related: mathoverflow.net/questions/46350/… |
|
Nov 29 |
comment |
If NP=EXPTIME, does every DTM have a succinct “execution proof”? Right, that's why I mentioned the complement in the first paragraph (although I failed to work it into the rest of the argument in a coherent way, sorry.) I guess you could also say this as "EXP=Co-EXP", but I don't think I've ever seen it put that way. I don't think it depends on NP=EXP, does it? |
|
Nov 29 |
revised |
If NP=EXPTIME, does every DTM have a succinct “execution proof”? make it clearer what part is the original post and what part is the edit |
|
Nov 29 |
awarded | ● Teacher |
|
Nov 29 |
asked | If NP=EXPTIME, does every DTM have a succinct “execution proof”? |
|
Nov 29 |
answered | Redundancy and Structure of computational problems |
|
Nov 29 |
awarded | ● Scholar |
|
Nov 29 |
comment |
How would one characterize a PR-complete language? Thank you, I found this quite elucidating. |
|
Nov 29 |
answered | Is complement of LL(k) grammar context free? |
|
Nov 28 |
awarded | ● Supporter |
|
Nov 28 |
comment |
How would one characterize a PR-complete language? Thank you. I was well aware of the non-existence of universal p.r. functions by the diagonalization argument; I think my confusion here is coming from trying to see PR as a complexity class and attempting to use complexity-preserving reductions to characterize it. |
|
Nov 28 |
revised |
How would one characterize a PR-complete language? changed tag to more popular "computational-complexity" |
|
Nov 28 |
awarded | ● Editor |
|
Nov 28 |
awarded | ● Student |
|
Nov 28 |
revised |
How would one characterize a PR-complete language? rephrased to express doubt about my candidate |
|
Nov 28 |
asked | How would one characterize a PR-complete language? |
