24
votes
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
There is an important class of primitive recursive functions. Citing Wikipedia,
[P]rimitive recursive function is roughly speaking a function that can
be computed by a computer program whose loops ...
- 887
11
votes
Accepted
Complexity classes pertaining to listing all solutions?
The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a ...
- 1,301
8
votes
Is it feasible to generate every possible RGB image?
The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not ...
D.W.♦
- 156k
8
votes
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
The primes can be recognized in linear space by a Turing machine. Linear space-bounded Turing machines are not universal. So, I think I have to disappoint you.
- 29.8k
7
votes
Accepted
Linear time algorithm for finding $k$ shortest paths from $s$ to $t$
First of all, the answer that applies here was already given by Raphael in the comments to the question: "Given that we don't even know how to find one simple shortest path in linear time, I doubt it."...
- 3,433
7
votes
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
Belated citation add: see Fischer or Gordon for more on essentially this line of thought.
As observed above, "locally" the problem of enumerating primes is very easy: the function sending $...
- 2,713
6
votes
Why aren't computables used for numerical calculations?
It sounds extremely inefficient compared to floating point. We have a very good understanding of how to control the errors in floating-point calculations (e.g., adding small numbers before large ones, ...
- 81.4k
6
votes
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
Yes. Friant [1] proved that the language $\{ a^p \mid p \text{ is prime}\}$ is a context-sensitive language, which is far stronger than recursively enumerable. My grandfather Benny Brodda [2] then ...
5
votes
If the strings of a language can be enumerated in lexicographic order, is it recursive?
Lexicographic order is not such a good order since its order type is not $\omega$. Instead of explaining formally what that means, let me give an example. Consider the language $(a+b)^*$. If you ...
- 275k
5
votes
Accepted
How to compute all primes between upto $n$ in time $O(n)$ time?
You can use a sieve to enumerate all prime numbers up to $n$. There are multiple algorithms; see the Wikipedia article I link for some examples. The sieve of Atkin and wheel sieves apparently run in ...
D.W.♦
- 156k
5
votes
Accepted
Proof that total computable functions are not enumerable
$g$ is total computable by definition.
By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable.
$1$ certainly is.
$+$ certainly is.
The concatenation of $+$ and $f$ is computable by ...
- 72k
4
votes
Accepted
Enumerating sets in a random order
Suppose that you have arrays $A_1,\ldots,A_d$ of sizes $n_1,\ldots,n_d$. The total number of tuples is thus $n_1 \times \cdots \times n_d$. Given a number in the range $1,\ldots,n_1 \times \cdots \...
- 275k
4
votes
Why aren't computables used for numerical calculations?
This probably isn't exactly what you're looking for, but perhaps nevertheless interesting.
There have been proposals for different kinds of computables, for example these by Bill Gosper: Continued ...
- 2,018
4
votes
Accepted
Enumeration of winning coalitions
You are asking two questions:
How to count "winning groups" up to isomorphism?
Which winning groups are realizable as winning coalitions?
From the point of view of winning groups, we can assume that ...
- 275k
4
votes
Accepted
Using reduction to prove that a given language is not recursively enumerable
Assume that $L$ is recursively enumerable. We can reduce the Halting problem to $L$ as following. Given $\langle M, w \rangle$, create a TM $M'$ which halts only on the input $w$, and infinitely loops ...
- 9,757
4
votes
Accepted
Which one of these two sets is computably enumerable?
As Rick commented, the first question is asking whether the set of Turing machines that recognize no more 330 strings is computably enumerable. Similarly, the second question is asking whether the set ...
- 38.6k
4
votes
Accepted
Enumerate over all halting Turing Machines?
The paper you're referring to is using "enumeration" just to mean "ordered list". Your feeling that such a list can't be computed by a Turing machine is correct. However, the list exists, even though ...
- 81.4k
4
votes
Is the following function computable? is it total?
Your function is well-defined, that is, total. The value of $f(n)$ is the maximum of the finite set $\{g_1(n), \ldots, g_{w(n)}(n)\}$. The maximum of a finite set of numbers always exists.
Your ...
- 275k
3
votes
Find all cycles through a given vertex
Solution: Modify Johnson's algorithm
Johnson's algorithm can be used to enumerate all cycles in $G$. It can be easily modified to enumerate only and all the cycles that contain $v$.
Johnson's ...
D.W.♦
- 156k
3
votes
Finding all faces in a wireframe mesh
After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work.
...
- 253
3
votes
Accepted
Find a string that covers many sets of binary strings with don't-cares
Your problem is NP-hard. It's basically a variant of SAT. You shouldn't expect any algorithm that is provably efficient. Instead, I recommend you use an off-the-shelf SAT solver; since your problem ...
D.W.♦
- 156k
3
votes
Finding all paths from s to t in linear time
The algorithm you describe cannot possibly be linear time for a DAG or general graph. Consider the following DAG on $n$ vertices $V = \{v_1, v_2, \ldots v_n\}$. Take a particular node $v_i$, for all $...
- 4,431
3
votes
Enumerate partitions of a set with blocks of equal size
Section 5.10 of Ruskey's book Combinatorial Generation gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear ...
- 2,072
3
votes
Accepted
Checking if the mimimum is unique
You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z_1,\ldots,z_n$:
$x,y < z_i$ for all $i$.
$x,y < z_i$ for all $i < n$, and $z_n < x,y$.
...
- 275k
3
votes
Proof that total computable functions are not enumerable
The problem really is in how you're approaching the proof by contradiction. You're objecting to one conclusion ("$g$ is computable and total") by drawing a different conclusion ("$g$ isn't total ...
- 2,713
3
votes
Enumerate over all halting Turing Machines?
If you mean halting TMs by TMs that are halt on all strings, then yes, it is impossible to enumerate over all halting TMs. However, this is not because the set of halting TMs is undecidable, but ...
- 7,395
3
votes
Number of possible heaps on $\{1,...,2^h-1\}$
The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$.
Instead of looking at ...
- 12.5k
3
votes
Accepted
Enumerate all paths in a given series-parallel graph
Treat SPG as DAG
We can see easily that every path from the source to the sink in a series-parallel graph (SPG) always goes nearer and nearer to the sink. It can never go backwards. There is no ...
- 38.6k
3
votes
Enumerate all solutions to integer programming problem
It's possible to enumerate all solutions, using a recursive algorithm that repeatedly invokes an integer programming solver. Basically, at each step, you pick a variable, find its range of feasible ...
D.W.♦
- 156k
3
votes
Accepted
Generating all equal-sized set partitions
Suppose $N=\{0,\dots,N-1\}$.
There are $\binom{N-1}{K-1}$ choices for which elements are equivalent to 0. For each choice of these there are $\binom{N-K-1}{K-1}$ choices for which elements are ...
Only top scored, non community-wiki answers of a minimum length are eligible