Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computer-science
Search options not deleted
user 4600
For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.
1
vote
scott continuity, sub additivity
Actually, the converse implication doesn't hold.
Let $X$ and $Y$ be posets with greatest elements $1_X$, $1_Y$, and let $\delta_x$ and $\delta_y$ be the constant $1_X$, $1_Y$ maps. These are clearly …
- 24.8k
8
votes
Accepted
Is there an unambiguous CFL whose complement is not context-free?
Yes, and the first published example is, in a 4-letter alphabet $\{a,b,c,d\}$, the set of all words $a^pb^qc^rd^s$ such that either
$$
(10p<q<12p\text{ or } 10q<p<12q)\text{ and } (10r<s<12r \text{ or …
- 24.8k
3
votes
Accepted
Self-similarity in the theory of computability
Yes, there is such a non-computable set $M$.
Let $M=(M(0),M(1),\ldots)$ be a bi-immune set (i.e., having no infinite computable subset, and whose complement has no infinite computable subset) of mini …
- 24.8k
2
votes
Efficiency of representations of number
The following assumptions seem natural:
Each natural number $0,1,2,\dots$ is to be represented by a nonempty binary string.
Smaller numbers are to have shorter representations.
No two strings should …
- 24.8k
11
votes
Accepted
Can a stochastic Turing machine output a consistent extension of PA with positive probability?
The answer is no, but it's almost yes. A stochastic Turing machine can find a diagonally non-computable ($\textsf{DNC}$) function ($f$ with $f(x)\ne\varphi_x(x)$ for all $x$) and finding a complete ex …
- 24.8k
6
votes
1
answer
350
views
Number of partitions whose blocks form arithmetic progressions
As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$.
A n …
- 24.8k
3
votes
Are limits decidable? Should definitions be decidable?
You're right, and moreover this is sharp, i.e., you cannot do more than compute the Halting Problem using limits of computable sets.
This is called the Limit Lemma in computability theory.
- 24.8k
11
votes
Can We Decide Whether Small Computer Programs Halt?
You're right that such a project is possible. Calude et al. (http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Calude361_370.pdf) have some results in this direction.
- 24.8k
7
votes
Which distributions can you sample if you can sample a Gaussian?
Just want to observe that if $X$ is $\mathcal N(0,1)$ and $Y$ has any distribution with a strictly increasing* cdf $F_Y$ such that $F_Y^{-1} \circ F_X$ is computable (in whatever model of computabilit …
- 24.8k
3
votes
What is the name for Boolean algebra's version of $\models$ between sets of identities and i...
It seems the name for this idea is equationally complete theory, see page 30 of Walter Taylor's Equational Logic survey.
Not every theory is like that:
for example in the theory of lattices, which is …
- 24.8k
8
votes
Accepted
Define Turing machine with algebraic concepts/structures
Yes, there is now Pavlovic's characterization of Turing computability in terms of the monoidal computer, based on monoidal categories. http://arxiv.org/abs/1208.5205
- 24.8k