Tag Info

24

Because of diagonalization. If $(f_e: e \in \mathbb{N})$ was a computable enumeration of all total computable functions from $\mathbb{N}$ to $\mathbb{N}$, such that every $f_e$ was total, then $g(i) = f_i(i)+ 1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no ...

15

Juho's algorithm can be improved to an $O(N)$ algorithm using meet-in-the-middle. Go over all pairs $A,B \leq \sqrt{N}$; for each pair such that $M=A^2+B^2 \leq N$, store $(A,B)$ in some array $T$ of length $N$ (each position $M$ could contain several pairs, which might be stored in a linked list). Now go over pairs $M,N-M$ such that the corresponding cells ...

13

This question appears to be very Googleable. For example, you may be interested in the algorithm presented in this paper: Finding all the elementary circuits of a directed graph. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975 Abstract. An algorithm is presented which finds all the elementary circuits-of a directed graph in time bounded by O(...

12

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

10

Just to be clear, we need to distinguish mathematical functions (I will call them functions and there is often uncountably many of them so they are not at all enumerable) and functions you can write: I will call them programs or also computable functions. A subset $S$ of a countable set $E$ is called computable if there is a program that, given an element $... 10 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 ... 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 ... 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 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 ... 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'm assuming that your definition of a computable number is this: there is a Turing machine that on input$n$, halts with the$n$th bit of the number. Suppose there were a recursive enumeration of Turing machines that produce computable numbers. You can use diagonalization to come up with a new computable number which isn't part of this recursive ... 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 I think a$o(N^2)$time algorithm is not a trivial one and requires some insight if one exists. The obvious algorithm that runs in quadratic time enumerates all tuples$A,B,C,D \leq \sqrt[]{N}$. This can be done in four loops, so the total time complexity becomes$O(N^2)$. It also clearly enumerates all solutions. As relating algorithms, Rabin and Shallit [... 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

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.

4

First, separate the set of variables $I = \{1,\dots,n\}$ according to their values: \qquad\begin{align} I_+ &= \{ i \mid X_i = 1\} \text{ and} \\ I_- &= \{ i \mid X_i = 0\} \;. \end{align} Let $n_+ = |I_+|$ and $n_- = |I_-|$. Given $X_1, \dots, X_n$ and $k$, it is clear that we have to choose $k$ indices from $I_+$ and arbitrarily many from $... 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 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

$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

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 ... 3 Multitape machines are equivalent to single tape machines. You can simulate several tapes on a single tape. In particular, in order to simulate the "print state" model using the "write-only output tape" model, you simulate an extra output tape, and whenever the print state is reached, you copy the contents of the extra output tape to the write-only output ... 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 ... 3 calculating/estimating/approximating the average path length has been studied for some random graph models including the Erdos-Renyi model and the Barabasi-Albert scale free networks, and also the Strogatz small world graphs which may be suitable as approximations for your graphs. [it would be better if you could narrow down/detail some nature/... 3 SUBSET-SUM instances can be encoded in base 3. We have codes for$0,1,\#$. Some codings are invalid, but in that case we can just immediately output$\#\#$(or$\#$, if we have just written$\#$). Every SUBSET-SUM problem has infinitely many encodings, I hope that's not a problem. If the input has length$\ell\$, then (assuming the tape alphabet has at least ...

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