24

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 are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). They are powerful ...


15

Here I assume $0\in \mathbb N$. If you disagree start with $105$. Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order. Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along ...


11

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 language/set). Enumeration algorithms can be modeled as a two step process:a precomputation step and an enumeration phase with delay. Both of these steps have their ...


8

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 feasible to enumerate all such images within the lifetime of the solar system. (There's something wrong with your reasoning if you've concluded it's reasonably ...


8

As observed above, "locally" the problem of enumerating primes is very easy: the function sending $n$ to the $n$th prime, $n\mapsto \mathsf{thprime}(n)$, is primitive recursive (and of course that's massive overkill). However, you specifically want a framework which allows programs to run forever. This complicates things a bit: in some sense we ...


7

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." In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I ...


7

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.


6

You can solve this with a priority queue. Let $L(x)$ be the log-probability of the vector $x$, i.e., $$L(x) = \log \prod_i p_i^{x_i} (1-p_i)^{1-x_i} = \sum_i \ell_i(x_i)$$ where $$\ell_i(b) = \log (p_i^b (1-p_i)^{1-b}).$$ Since the log is monotone, your problem is equivalent to looking for a way to enumerate the vectors $x \in \{0,1\}^n$ in order of ...


6

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, avoiding taking the difference of large numbers and so on) so the only benefit of the methods you're suggesting would appear to be that they offer increased ...


5

I can't make heads nor tails from what you attempt to do, but I know that the answer to your question is: no, NP is not enumerable. First, let's fix what that means. I assume you are asking if $\qquad\displaystyle \mathrm{TM}_{\mathsf{NP}} = \{ \langle M \rangle \mid L(M) \in \mathsf{NP} \}$ is recursively enumerable. It's not by the extended Rice theorem ...


5

You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call. $f(i,j) = \begin{cases} \emptyset & if\ \ {i>j}\\ \emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\ \{(n,n)\} & if \ \ i = ...


5

Consider a weighted, directed graph, with a vertex $v_i$ for $i\in\mathbb{N}$. There is an edge with weight $j-i$ from $v_i$ to $v_j$ if $j\in\{3i,5i,7i\}$. Now run Dijkstra's shortest path algorithm. It will expand exactly the nodes from your sequence and do so in order. This gives an $n\log n$ algorithm to enumerate the first $n$ elements, since the graph ...


5

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 $O(n)$ time.


5

$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 construction, and that's $g$. The details depend on the exact definition of "computable" (i.e. the machine model) you use; see e.g. here. So under the assumption ...


4

For the $k$ shortest paths, there are algorithms; see for instance here. Enumerating all shortest paths is, however, an inherently costly thing; there may be superexponentially many such paths.


4

Let $P(i, j)$ be the number of paths from the start node, $(0,0)$, to the destination node, $(i, j)$. Then it's easy to see that $$\begin{align} P(i, 0) &= 1\\ P(0, j) &= 1\\ P(i, j) &= P(i-1,j)+P(i-1,j-1)+P(i, j-1), \text{ if }i,j>0 \end{align}$$ Applying this recursion directly isn't particularly efficient, since you'll wind up making a lot ...


4

It is somewhat more natural to normalize the number of bit changes per step by the number of steps, namely $2^n-1$. We can then rephrase your question as follows. Let $\pi$ be a random permutation of $\{0,1\}^n$. You are interested in the distribution of $$ X = \frac{1}{2^n-1} \sum_{i=0}^{2^n-2} d(\pi(i),\pi(i+1)), $$ where $d$ is Hamming distance. We can ...


4

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 each voter always casts all her votes, and the resulting games is known as a weighted voting game. Counting winning groups Your concept of "winning group" is ...


4

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 enumerate the words in lexicographic order, you get $$ \epsilon, a, aa, aaa, \ldots, ab, \ldots $$ The first $\ldots$ signify infinitely many terms. So it isn't ...


4

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 \times n_d$, you can decipher it into a tuple (I leave this part to you). It now remains to compute a pseudorandom permutation of the numbers $1,\ldots,n_1 \times \...


4

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 Fraction Arithmetic (hardware support is described at the bottom, for Continued Logarithms). Doing calculations in software with continued fractions has seen ...


4

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 of Turing machines that recognize no less 330 strings is computably enumerable. Let us show that second set is computably enumerable using dovetailing. Let $...


4

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 there's no algorithm that will tell us what its members are. Also, note that it refers to "an enumeration of halting Turing machines", not "an enumeration of ...


4

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 gave an improved grammar for this purpose in 1968, which: contains a smaller number of rules; the rules are not so context-dependent; and finally, there are no `...


4

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 function is computable iff $w$ is bounded. Suppose first that $w$ is not bounded, and assume for the sake of contradiction that $f$ were computable. Then $h(n) = f(n) ...


3

It's not possible to solve this problem "efficiently". There can be exponentially many paths of a given length, so enumerating all of them is not feasible in large graphs. Your dynamic programming approach is a pretty good one, though you might be able to improve it by not storing the paths explicitly but instead storing the paths as linked lists or using ...


3

Use recursion. Something like this: def f(l, k): if l==0: yield [] else: for i in range(k): for L in f(l-1, k): yield [i]+L Here f(l, k) produces all lists of length l all of whose entries are in the range 0..k-1. The idea is that if you have all lists of length l-1 (the output of f(l-1, k)) you can use ...


3

One approach would be to enumerate all graphs of a given size, then test each one to see if it is planar and filter out the non-planar ones. This might work acceptably if you only want very small graphs. Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly. There are ...


3

Here's another way of looking at the problem: You have a lattice generated by the columns of $M$. Use the Lenstra–Lenstra–Lovász (LLL) algorithm to obtain a reduced basis of this lattice. If you replace $M$ by a new matrix formed by the output of LLL, then the columns of $M$ will still generate the same lattice, but the basis vectors will be closer to being ...


3

Idea: Root the tree in an arbitrary node. For every node, count paths in its subtrees, paths that start in a subtree and end in the root, and paths that start in one subtree, traverse the root and end in another subtree. That is, for a given node $v$ with children $u_1, \dots, u_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the ...


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