bio | website | lshap.blogspot.com |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 10 months |
seen | May 12 '12 at 1:45 | |
stats | profile views | 128 |
Code monkey with some knowledge about computation.
Sep
24 |
awarded | Autobiographer |
Jan
18 |
awarded | Popular Question |
Apr
26 |
comment |
“Simpler” statements equivalent to Con(PA) or Con(ZFC)?
Btw, are we all certain that the required state count of a theorem-enumerating TM is essentially that of any context-free grammar generator? Might the first-order logic inference rules be easier/harder to apply? |
Aug
8 |
comment |
Succinctly naming big numbers: ZFC versus Busy-Beaver
Here's the problem. If you write "x = BB(n)" as a proposition in the language of ZFC with x as its free variable, then the ZFC axioms aren't sufficient to pin down a single value that x must have. So "the value of x defined in ZFC by 'x = BB(n)'" isn't a well-defined entry for Scott's contest. But if we just talk about Turing machines as their own meta-level thing, then "BB(n)" is a well-defined integer for Scott's contest. |
Aug
6 |
awarded | Teacher |
Aug
6 |
revised |
Succinctly naming big numbers: ZFC versus Busy-Beaver
added 2 characters in body |
Aug
6 |
revised |
Succinctly naming big numbers: ZFC versus Busy-Beaver
edited body; deleted 26 characters in body |
Aug
6 |
answered | Succinctly naming big numbers: ZFC versus Busy-Beaver |
Mar
25 |
awarded | Supporter |
Oct
24 |
comment |
Characterize P^NP
Thanks for the great answer! |
Oct
24 |
accepted | Characterize P^NP |
Oct
24 |
awarded | Student |
Oct
23 |
awarded | Scholar |
Oct
23 |
awarded | Editor |
Oct
23 |
revised |
How can one characterize NP^SAT?
deleted 58 characters in body |
Oct
23 |
asked | Characterize P^NP |
Oct
23 |
comment |
How can one characterize NP^SAT?
Yes you are obviously right, I actually got confused with another question I meant to ask instead about P^NP. |
Oct
23 |
accepted | How can one characterize NP^SAT? |
Oct
23 |
asked | How can one characterize NP^SAT? |