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

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

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

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

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

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

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