**0**

votes

**1**answer

252 views

### Universality of blind graph rewriting

Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed
graph with the set of nodes $M$, which has ...

**3**

votes

**2**answers

360 views

### Representation of μ-recursive functions

Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function?
According to Wikipedia, any μ-recursive function can be expressed as the ...

**3**

votes

**1**answer

817 views

### Algebraic structure generated by primitive graph operations

Let $M$ be a finite set, and
$S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$.
Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has exactly two arrows ...

**31**

votes

**12**answers

2k views

### Interesting conjectures “discovered” by computers and proved by humans?

There are notable examples of computers "proving" results discovered by mathematicians, what about the opposite:
Are there interesting conjectures "discovered" by computers and proved by humans?
...

**3**

votes

**2**answers

1k views

### symmetric difference of languages - both are in NP and coNP

I have this problem,
Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:
$L_1 \oplus L_2$ = {x | x is in exactly one of $...

**29**

votes

**0**answers

771 views

### Computer calculations in A_infinity categories?

Is there a good computer program for doing calculations in A-infinity categories?
Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep ...

**7**

votes

**2**answers

996 views

### Busy Beaver - Proof for BB(2) = 4

Hi,
I need to prove the above claim.
I can show that $BB(2)\ge 4$ by building a turing machine,
but how can i show that $BB(2) \le 4$?
Searched a lot over the web, and saw that Rado proved it in ...

**3**

votes

**2**answers

747 views

### Certain type of regular languages

Dear All,
there is one type of regular languages, over $\{a,b\}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characterisation, that ...

**3**

votes

**2**answers

989 views

### Kleene's fixed point theorem on recursive subsets of computable functions

I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have ...

**5**

votes

**1**answer

447 views

### Arrangement of integers 1..k^2 in k*k grid to minimize energy function

Question arises from considering cache oblivious algorithms.
What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring squares?...

**7**

votes

**3**answers

663 views

### Error correcting codes - basic question

Hi,
I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), ...

**25**

votes

**4**answers

1k views

### A programming language that can only create algorithms with polynomial runtime?

Has someone constructed a programming language that can construct all the algorithms in P, and no others?
I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...

**2**

votes

**2**answers

611 views

### Graph Theory Conjectures [closed]

What are some important conjectures in graph theory that have been checked by computer up to order 11?

**6**

votes

**1**answer

365 views

### compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...

**2**

votes

**0**answers

108 views

### How to argue about state transitions?

Computing differs from math by its dependence on state changes, among other things. A program can be seen as a composition of state transitions, and it would be nice to have an inverse function to ...

**2**

votes

**1**answer

612 views

### Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...

**1**

vote

**2**answers

547 views

### Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?

Every proof I've read about this fact considers two cases: $A$ - finite and $A$ - infinite but this is undecidable problem. So, is there constructive proof?

**8**

votes

**2**answers

356 views

### Reduction rules for inductive types

(I'm not sure if I should post this here rather than at Theoretical Computer Science, I've found a lot of type theory related questions on MathOverflow)
I'm working in Martin-Löf type theory with ...

**0**

votes

**1**answer

154 views

### Subset-Free Codes

For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order: $\;\;$ 1. $\;$ have the most elements $\;\;$ 2. $\;$ minimize the maximum of its elements' sum of ...

**6**

votes

**2**answers

2k views

### Is there any math foundation for map/reduce?

For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication.
First, this is not exactly how monoids work, and second, this ...

**5**

votes

**2**answers

236 views

### What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title:
What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?
Imagine I have some non-convex polyhedron $P$, and I would like to ...

**7**

votes

**2**answers

882 views

### Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...

**16**

votes

**1**answer

3k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...

**4**

votes

**1**answer

876 views

### Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?
For example, consider $K_4$ with vertices $V=${1,2,3,4}...

**2**

votes

**1**answer

201 views

### Recoving an unknown tree graph with knowledge of root node to leaf node distances

Imagine I have an unknown (undirected) tree graph, $G$, with some unknown number of nodes $||V||$. However, I know the edge-length between nodes is of fixed size, $L_{edge} = 1$, and I have access to ...

**4**

votes

**1**answer

270 views

### Inverse of Kleisli star, or “extension operator”

While thinking about monads in the theory of denotational semantics, I have made an observation about the Kleisli category that I would like to check
Suppose $F : \mathcal D \to \mathcal C$, $G : \...

**3**

votes

**1**answer

281 views

### Hermit H-machines

I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...

**2**

votes

**2**answers

482 views

### Threading pinholes in the wall of cylinder to pass through an internal coordinate

Imagine I take a sheet of paper and use a pin to generate an $N$x$M$ rectangular array of small holes. I then fold the sheet to form a cylinder of radius $r_c$ and height $h_c$, where there are $N$ ...

**1**

vote

**1**answer

235 views

### Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without “being able to know” one of the discrete logs involved (formal definition given in question)?

Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...

**1**

vote

**0**answers

130 views

### Optimizing for a unique outcome of a probabilistic marriage problem

Let's say I have some number of individuals who are single, $(b_1, ..., b_N) \in B$, and for every possible pairing of two individuals, $b_i$ and $b_j$, I happen to know the exact probability that the ...

**0**

votes

**1**answer

222 views

### Is there a name for a formula to calculate ascending numbers to a quadratic-like sequence?

For e.g. any range of number 0 - n
0 1 2 3 4 5 6
to:
0 2 4 6 4 2 0
Is there a name for this kind of formula or calculation?

**5**

votes

**3**answers

986 views

### Estimating the fractal dimension of a point cloud

I have finite set of geolocation point data, and I'd like to estimate the fractal dimension. I know there are several ways to do this, and some of them give different numbers. What is the most ...

**2**

votes

**1**answer

337 views

### Complexity of computing derivatives

Sorry if this is too simple. This is my first question here.
Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point $...

**3**

votes

**1**answer

282 views

### Numerical Beta Function

Anyone know a fast and concise way of calculating the Beta $B(a,b)$ function for smallish (<10) real $a$ and $b$.
For integer $a$ and $b$ I have:
$B(a,b) = \prod\limits_{j=1}^b \frac{j}{a+j}$
...

**7**

votes

**1**answer

303 views

### RAM simulating another RAM

(Cross-posted from cstheory-stackexchange)
The following fact seems to be used implicitly in cs theory, particularly algorithms. Given a RAM machine $M$ running in time $O(f(n))$, another RAM machine ...

**-1**

votes

**1**answer

879 views

### Transition Graph per alphabet? [closed]

How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...

**2**

votes

**1**answer

2k views

### How many cpus needed to check a 100 million digit prime number efficiently? [closed]

If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...

**1**

vote

**3**answers

433 views

### Operator probability in a RPN string

Consider the set $S_n$ of all strings of length $n$ ($n$ integer, $n \geq 3$)
representing an expression in RPN
( http://en.wikipedia.org/wiki/Reverse_Polish_notation. )
Assumptions (to simplify):
...

**1**

vote

**2**answers

580 views

### Hash functions and inner product

Hi all,
As a part of a research I'm working on (involving derandomization of linear threshold functions), I'm trying to understand the following problem:
Is there a small (polynomial rather than ...

**1**

vote

**1**answer

496 views

### Decomposing a sphere (or defomed sphere) into a vertex-transitive graph with fixed-length curved edges

Please see the original problem specification (which Joseph O'Rourke was responding to in his answer) below.
Motivation -
I'm interested in a particular case of the problem where one wants to ...

**1**

vote

**0**answers

228 views

### Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from
http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there)
The following ...

**1**

vote

**1**answer

268 views

### Constructing a graph that approximates a sphere using rotationally symmetric building blocks with equal numbers of edges

I'd like to construct a graph that approximates a sphere in 3-space, but I'm placed under the following constraints:
(1) - I am only allowed to use a construction block, $v_i$, consisting of a single ...

**7**

votes

**6**answers

6k views

### Fast evaluation of polynomials

Hello everybody !
I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...

**1**

vote

**1**answer

134 views

### Inferring geometric properties of a polytope from intersection volumes of spheres at unknown coordinates on its surface

Let's say we have some polytope $P$ in 3-space (which is not necessarily convex) as well as some number of points on its surface, $(g_1, ..., g_N)$. We are provided no information about the ...

**1**

vote

**0**answers

349 views

### NP-complete variants of NPI problems

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...

**8**

votes

**1**answer

526 views

### Magma “actions” (or alternatively, “What is the Yoneda lemma for magmas?”)

Arguably the most import thing about groups, semigroups and more generally categories, is that they can act on sets (or even collections of sets in the case of a category). This is the basis for all ...

**6**

votes

**1**answer

382 views

### Growth zeta-functions of regular languages

Dear All,
my following question may be known and ought to be known, so in case it is folklore please could you give me the references.
To start, it is obvious that growth of rational languages are ...

**7**

votes

**1**answer

744 views

### The hardness of computing inverse

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input.
Are ...

**2**

votes

**1**answer

328 views

### Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...

**2**

votes

**1**answer

463 views

### Lipschitz constant of Laplace-Beltrami Operator

I already asked this question at stackexchange with no response - so I'll try here.
I'm reading a paper on discrete differential geometry:
Meyer et.al.
They define the Laplace-Beltrami operator at ...