Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Ivan Smirnov's user avatar
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 ...
mdxn's user avatar
  • 1,301
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.
Hendrik Jan's user avatar
  • 30.7k
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."...
Carlos Linares López's user avatar
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 $...
Noah Schweber's user avatar
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, ...
David Richerby's user avatar
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 ...
Carl-Fredrik Nyberg Brodda's user avatar
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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 161k
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 ...
Raphael's user avatar
  • 72.5k
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 ...
Yuval Filmus's user avatar
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 \...
Yuval Filmus's user avatar
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 ...
user555045's user avatar
  • 2,053
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 ...
fade2black's user avatar
  • 9,837
4 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 ...
Noah Schweber's user avatar
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 ...
John L.'s user avatar
  • 39k
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 ...
David Richerby's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Peter Taylor's user avatar
  • 2,082
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 $...
ryan's user avatar
  • 4,511
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. ...
hgs3's user avatar
  • 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.'s user avatar
  • 161k
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.'s user avatar
  • 161k
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$. ...
Yuval Filmus's user avatar
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 ...
xskxzr's user avatar
  • 7,455
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 ...
Nathaniel's user avatar
  • 15.7k
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 ...
John L.'s user avatar
  • 39k
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.'s user avatar
  • 161k
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 ...
Bjørn Kjos-Hanssen's user avatar
3 votes
Accepted

Number of parenthesizations and Catalan numbers

Define function $Q:\mathbb N\to\mathbb N$ such that $Q(n)=P(n+1)$ for all $n\ge 0$. Or, what is equivalent, $P(n)=Q(n-1)$ for all $n\ge 1$. We have $$Q(0)= P(0+1)=P(1)=1.\quad\quad\quad\quad\quad\...
John L.'s user avatar
  • 39k

Only top scored, non community-wiki answers of a minimum length are eligible