**9**

votes

**0**answers

255 views

### Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...

**0**

votes

**1**answer

190 views

### hypergraph cartesian join operation (over same vertex set)

consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph ...

**3**

votes

**2**answers

244 views

### What categories correspond to the typed lambda calculus with parametric types?

the unadorned typed lambda calculus correspond to the closed cartesian categories, but if we add in dependent or parametric types how are they then characterised?

**3**

votes

**0**answers

313 views

### Groupoid interpretation of type theory

Hello,
I read the paper on groupoid interpretation of type theory by Hofmann and Streicher and I have a question. According to the authors $Tm([[\text{Set}\:[\Gamma]\: ]])$ is the same as ...

**0**

votes

**1**answer

249 views

### Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT
(since 2SAT is polynomial, the algorithm is polynomial).
Can't prove completeness of the algorithm and since it is ...

**0**

votes

**0**answers

85 views

### Exact Length Problem in a directed graph

I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the ...

**4**

votes

**1**answer

486 views

### Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...

**5**

votes

**1**answer

626 views

### How much does a quantum oracle to find a needle in a haystack really cost?

Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance.
Grover's algorithm ...

**9**

votes

**3**answers

1k views

### Higher categories as data structures

Still wading through higher category theory. I find the subject a bit intimidating, not so much for technical reasons, but because I lack sufficient intuition as to the motivation(s)/heuristics one ...

**6**

votes

**1**answer

416 views

### Who introduced the concept of Primitive recursive functions?

I have thought that Gödel introduced the concept of Primitive recursive functions in his seminal paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (I hope I ...

**6**

votes

**0**answers

147 views

### Finding a database of representations as matrices

Sorry if this would be more appropriate as a stackoverflow and not a mathoverflow question, but I think it's more likely to be known in this community.
There are plenty of places on the internet or ...

**1**

vote

**2**answers

260 views

### Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say:
< is a strict partial order and R is an irreflexive and ...

**4**

votes

**3**answers

285 views

### Existential quantification over regular predicates

A regular language over an alphabet $\Sigma$ is a subset of the set of all words over $\Sigma$ that can be accepted by some finite automaton. A regular language identifies a certain property of ...

**7**

votes

**0**answers

233 views

### Modelling the difficulty of mental calculation. [closed]

Are you aware of any work that tries to model the difficulty of evaluating a formula mentally (for your average, numerate, person, not a trained mental calculator)?
For instance, evaluating an ...

**0**

votes

**1**answer

278 views

### Is there any relationship between a tree(graph theory) and semi-metric?

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?

**20**

votes

**4**answers

1k views

### Algorithmically unsolvable problems in topology

This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various ...

**3**

votes

**2**answers

338 views

### anyone help me with this inequality

I'm have some difficulties in bounding the following inequality:
I want to find a c as small as possible s.t.
$$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq ...

**3**

votes

**2**answers

940 views

### Is there an algorithm that can “reverse engineer” a Regular Expression?

Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces that language?

**5**

votes

**0**answers

193 views

### Büchi automata with acceptance strategy

I have already asked this question on cstheory.stackexchange, but without success. Maybe it is too close to an "open problem", although it is not a famous one. Anyway I try here, I can always remove ...

**2**

votes

**1**answer

325 views

### Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...

**0**

votes

**0**answers

343 views

### Examples of Hamiltonian Cycle Problem / Traveling Salesman Problem in general grid graph form

I understand that there is a polynomial algorithm to solve TSPs that are in solid grid graph form (grid graphs without holes).
I am particularly interested in the non-solid grid graph form of the ...

**3**

votes

**1**answer

188 views

### Bezier Curves question

Hi everyone
I have a fairly simple question about bezier curves: can you represent n bezier curves that have been continuously joined together by a single bezier curve of degree 3n?
My instinct is ...

**2**

votes

**1**answer

454 views

### #P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...

**0**

votes

**1**answer

244 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

330 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

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

**23**

votes

**11**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

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

**25**

votes

**0**answers

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

**6**

votes

**2**answers

862 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

732 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

590 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

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

**7**

votes

**3**answers

595 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), ...

**21**

votes

**4**answers

981 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

536 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

319 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

106 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

466 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

436 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

306 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

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

**6**

votes

**2**answers

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

**4**

votes

**2**answers

202 views

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

The question is mostly in the title.
Imagine I have some non-convex polyhedron $P$, and I would like to find the smallest diameter ring that it can pass through in 3-space, undergoing any necessary ...

**7**

votes

**2**answers

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

**12**

votes

**1**answer

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

**3**

votes

**1**answer

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

**1**

vote

**1**answer

188 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

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

**4**

votes

**1**answer

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