# Tagged Questions

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

233 views

### Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive?

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive ? I'm not particularly interested in a detailed proof or counterexample, just a quick argument why this affirmation should ...
337 views

### If P/Poly does not contain NP then does SAT require super-polynomial circuits?

I have a basic question about circuit complexity. Apparently no example of a language that requires super-polynomial circuits to decide is known. (This is despite the fact that an easy counting ...
1k views

### How can I prove that this set is recursively enumerable?

Let $g _c (x)$ be the output of a program that is encoded by $c \in \mathbb{N}$ for the given input $x$. $g_c$ can obviously be undefined, in case the program encoded by $c$ doesn't halt. If we define ...
65 views

### Identities for relations of the form (a,b). If it holds, how do you “prove” it?

First some context (binary relations) $F \subseteq W \times X \quad G \subseteq X \times Y \quad H \subseteq Y \times Z$ Does the following equality hold $(G \circ F)^{-1} = F^{-1} \circ G^{-1}$ ...
198 views

### Why can't we diagonalize out, if we deal with partial functions?

We know, that all (partial) recursive functions are countable (since one can for example interpret them as some simple programs; and the set of those programs are themselves countable), so one can try ...
156 views

### Uniform PRNG for long integer structures

Good morning! I don't actually know where to attribute this question (maybe it's better to publish it on StackOverflow), but it's more related to math theory than to actual realization. Since the ...
212 views

### A Function That Creates “Hello World!” [closed]

The classic string "Hello world!" can be translated to list of characters with ascii-codes: [72; 101; 108; 108; 111; 32; 87; 111; 114; 108; 100; 33] Is there a ...
197 views

### How do we know that there is a function from $\mathbb{N}$ to $\mathbb{N}$ that is not partial computable?

A partial computable function is also known as effectively computable, and is defined as any function that can be computed by a Turing machine with $Dom(f) \subseteq \Sigma^*$, where $\Sigma^*$ is the ...
175 views

### Terminology, mapping a tree to a tree

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
241 views

### What is the power of a recursive language vs. that of one that is recursively enumerable?

I am simply wondering, as the title states, what the central differences are between recursive and recursively enumerable languages? If I am not mistaken a recursive language is a is Turing decidable ...
2k views

### Probability of collision in binary exponential backoff

Four stations are trying to transmit frames through a single channel (only one frame per channel). After each frame is sent, they contend for the channel using Binary Exponential Backoff. After $i$...
640 views

### What is a good language to develop in for simple, yet customizable math programs?

I'm writing to ask for some guidance on choosing a language and course of action in learning programming. I've seen thread after thread with questions from newbies, asking, "What is the best language ...
151 views

14k views

### What does it mean to say a language is context-free?

What does it mean to say a language is context-free?
151 views

### Diagonalizations and their relation to P and NP

I'm quoting the following (landmark) paper: Theodore Baker, John Gill, and Robert Solovay Relativizations of the P?=NP Question SIAM Journal of Computing, Volume 4, Number 4, December 1975, ...
124 views

### On TM's with a single loop

Thinking about the halting problem for TM's, I came up with a statement that I can't prove or disprove easily and would want your suggestions. Conjecture: Given a TM whose digraph has a single cycle ,...
372 views

### Rank of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
591 views

### Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...
1k views

### What is undecidability

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?...
216 views

### Does this number exist?

Consider the finite algorithm A, and the real number $0<T<1$. The output of A on input T is all possible theorems and provable propositions in ZFC, and only that. Q1. Can such an algorithm and ...
206 views

### Common algorithm with an order of Θ(2^n)

What would be a common algorithm with an order of Θ(2^n)? When I say "order", I mean time complexity analysis. I was thinking exponential growth but are there any that are more computer science ...
173 views

### Find the missing term

The sequence $10000, 121, 100, 31, 24, n, 20$ represents a number $x$ with respect to different bases. What is the missing number, $n$? This is from my elementary computer aptitude paper. Is there ...
532 views

### balanced 2-partition with equal cardinality (cardinality difference = 1 (max))

Given a set $S$ of $N$ numbers, my aim is to partition it into two sets ($S_1$ and $S_2$), so that (i) the difference $\sum S_1 - \sum S_2$ is minimized and (ii) the difference $|S_1| - |S_2|$ is $1$...
387 views

### How to solve recurrence relations with emphasis on algorithmic complexity

I am having trouble solving recurrence relations, probably because I am missing the basics. Is there any web reference/book I can read to help me cover the basics? I watched some lectures and read ...
6k views

### fast algorithm for solving system of linear equations

I have a system of linear equations, $Ax=b$, with $N$ equations and $N$ unknowns ($N$ large) If I am interested in the solution for only one of the unknowns, what are the best approaches? for ...
303 views

### Deriving an expression for an epipolar line

I would like to derive an expression for an Epipolar Line that appears in a right camera (there are two cameras - a left a right one). These cameras are placed in a $(x,y,z)$ vector space. This is a ...
549 views

### Regular Language Notation Language

What I would like to do is design a program (for academic purposes) which will take a representation of a DFA (as a directed graph) and display the regular language which it accepts, in a reasonable ...
1k views

### What is the complexity of succinct (binary) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a ...
2k views

### Dijkstra's algorithm using heap

My teacher gave me a pseudocode of Dijkstra's algorithm using binary heap including the following steps (x was just extracted from the heap): For each vertex y such that it is a node for it in a ...
922 views

### Is this function a primitive recursive function?

Let $t \in \mathbb{N}$ and consider the function $f: \mathbb{N} \rightarrow \mathbb{N}$, defined by $f_t (m)= 2 \uparrow^{m} t$, where "$\uparrow$" is Knuth's up-arrow notation (which can be ...
57 views

### Probabilistic performance guarantees on information retrieval queries

The following is a question from lecture notes and although not assigned homework, I am trying to solve it. Assume that we have a collection $C$ of $N$ documents and a query $q$. There are $R_{q}$ ...
763 views

### Incremental calculation of inverse of a matrix

Does there exist a fast way to calculate the inverse of an $N \times N$ matrix, if we know the inverse of the $(N-1) \times (N-1)$ sub-matrix? For example, if $A$ is a $1000 \times 1000$ invertible ...
217 views

### Rank of a graph matrix

$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$. There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
4k views

### How to show that $ALL_{DFA}$ is in P

How can I show that $ALL_{DFA}$ is in P ? $ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
325 views

### Recognizing language using Turing machine

Given integers $a, b, c$ construct a single-tape Turing machine recognizing the language $\{w \in \{0,1\}^{*}: a*\#_{0}w+b*\#_{1}w+c=0\}$ in time $O(n*logn)$, where $n=|w|$. $\#_{x}w$ denotes the ...
335 views

398 views

### Decidable? Turing machine runs X steps for certain input?

Question is the following language decidable: {(M)|given input "aaaaa" Turing machine M will perform at least 1295 steps} I would say, yes it is. Just let the Universal Turing Machine count each ...