Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### 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
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

### 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.
• 30.7k
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,463

• 278k

### 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,053
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,837

### 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,783
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 ...
• 39k
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.8k

### 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 ...
• 278k