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

239 views

### Pumping lemma usage

I need to know if my solution for a problem related with regular languages and pumping lemma is correct. So, let $L = \{a^ib^jc^k \mid i, j,k \ge 0 \mbox{ and if } i = 1 \mbox{ then } j=k \}$ Now i ...
5k views

### Computational complexity of computing the determinant

The formula for the determinant of an $n$ by $n$ matrix given by expansion of minors involves $n!$ terms. As such, computing the determinant of a given matrix of with integer entries via expansion by ...
201 views

### Using base-2 numbers: $(1010001)_{2}/(11)_{2}=?$

I wanna solve this simple equation using base-2 number system. $(1010001)_{2}/(11)_{2}=?$ I can't remember how to do that, normally I would start with $101/11$ but what should I do this base-2 ...
740 views

2k views

### Every language is regular?

Could anyone tell me the error in my reasoning: The set of strings of a given alphabet is a countable set. Every string can be determined by a regular language. The union of two regular languages is ...
76 views

### inapproximability within $1+n^{\epsilon}$

I am a bit confused with the notation of an optimization problem not being approximable within a factor of $(1+n^{\epsilon})$. What exactly does this mean? I am confused because if I (as a user of ...
294 views

### The minimal number of states required to run Goldbach's Conjecture

It is well known that being able to compute Busy Beaver numbers would allow one to solve (in theory) such open problems as Goldbach's conjecture. Simply run a Turing machine with $n$ states to check ...
367 views

### Regular expressions which first disagree after an exponential length

Problem 8.24 of Sipser's Introduction to the Theory of Computation asks: For each $n$, exhibit two regular expressions $R$ and $S$ of length $poly(n)$ where $L(R)\not =L(S)$, but where the first ...
82 views

### Can every even natural number n be written as $\sum^N_{i=1}2^i\cdot f(i)$, where $f(i)$ is either zero or one?

This seems like something that should be trivial but I am having trouble showing it.
305 views

### Is an abstract machine Turing-complete if it can simulate itself?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
2k views

### Nondeterministic PDA to Deterministic PDA

Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going ...
475 views

### Fake Proof that $\mathrm{NP}^\mathrm{NP} = \mathrm{NP}$

I found this faulty proof of $$\newcommand{\NP}{\mathrm{NP}} \NP = \NP^{\NP},$$ where the tricky part is to proof that $\NP ^{\NP} \subseteq \NP$, and this is how it is realized: Take $\NP^\NP$ ...
756 views

### Is there a simple algorithm to generate unlabeled graphs?

While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
3k views

### Parity Checking and truth tables

I have a question that I am very confused about. Parity Checking. Produce a truth table for a parity checking circuit that is based on $4$ input data bits, an input parity bit and a single ...
348 views

### Properties of computable numbers

If we enumerate* all the computable numbers, those for which there exist a turing machine that outputs its digits to arbitrary precision. What is known about the asymptotic density of rationals, ...
8k views

### Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
719 views

### Proof that a multiplication verification can be done in log space

In Sipser's Introduction to Theory of Computation, he asks us to show that the language $MULT=\{(a,b,c):ab=c\}$ with $a,b,c\in\mathbb{Z}^+$ can be decided in log space. I originally started out with ...
188 views

### Merlin-Arthur complexity class for function problems

Quoting wikipedia, the complexity class $MA$ is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol where Merlin's only move precedes any computation by ...
926 views

### bitwise operations

so my question is what is the order of operations for bitwise operators << & | and also to see if my logic is right with the problem below (x03 << x08)+ x00 = 300 ((...
105 views

### Searching name for string concatenation problem

I am basically only looking for a name of a problem so I can find information about it. A friend of mine explained it to me like this: Given is a set of string variables $(x_1, \ldots, x_n)$, and a ...
92 views

### Size of an NL TM

On page 325 of Sipser, he gives a proof that PATH is NL-Complete which says basically that we can create a graph where each node is a configuration of a TM, and then solving if a path exists ...
2k views

### How can I learn about proofs for computer science?

I study computer science at a university. My school offers several courses where various proofs are expected, but there is no course that introduces the fundamental concepts of proofs and how to write ...
2k views

### Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
77 views

### Efficiently deciding if any of a set of cylinders in 3-space intersect

Let's say I have a set $C$ of $N$ cylinders in 3-space, $(c_1, ..., c_N) \in C$, where each cylinder, $c_i$, has an associated radius $r_i$ and two coordinates specifying the endpoints of the line ...
729 views

### How to determine if a graph is 3-colorable, given a way to determine for any graph if removing an edge from that graph gives a 3 colorable graph?

The question is rather explicit, but I will restate it here: Given the ability to determine whether there is an edge that can be removed from a given graph to give a 3-colorable graph, how can I find ...
165 views

### Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
2k views

### Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
568 views

165 views

### Reduction over intersection of languages

Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$. 1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to ...
658 views

### Always oddly-many ones in the binary expression for $10^{10^{n}}$?

Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even). Let $q(n)$ be the number of ones in the ...
116 views

327 views

### Comp Sci Math; Hamming Distance

I've been tasked with this question but I have no idea how to answer it. What is the maximum possible hamming distance between two points from level i in a n-cube?
615 views

### Directed Graph, shortest path algorithm. I don't even understand what this question is asking. Is it a trick question or just Dijkstra's?

Consider a directed graph with each edge assigned a nonnegative weight D that reflects the difficulty of passing over that edge (perhaps modeling an obstacle course). Define the difficulty of a ...
268 views

### Need to express curves as a set of gaussians, and compare two of these sets

I have two xy curves, defined numerically on a given (potentially different) range of x coordinates. What I need to do is to compare these two curves with the following strategy: express each curve ...
1k views

### What about Genetic Algorithms from a mathematical point of view?

Last year I've attended an Artificial Intelligence course (it was very simple, just a summary of the main ideas); we've seen what a genetic algorithm is and the idea seems very interesting to me. Now ...
3k views

I am very interested in learning about audio from a signal processing standpoint. However, whenever I try to further my education by reading books, I get extremely frustrated because the books use ...
428 views

### How do I generate the set of binary strings with elements that are unique under reversal?

What is the most efficient way to generate the set $S$ of unique binary strings of a certain length, $L$, s.t. all strings are unique under the reversal operation? For example, if $L = 2$, the ...
1k views

### CRC computation

I would like to understand the CRC computation using CCITT CRC-16 $x^{16} + x^{12} +x^{5} +1$. I was able to successfully implement it in a program but I would like to understand the computation ...
162 views

### Regular expression $baa \in a^*b^*a^*b^*$: is that true or false?

Could someone please guide me how to go about solving this problem? $$baa \in a^*b^*a^*b^* .$$ The question asks whether string $baa$ is an element of $a^*b^*a^*b^*$ (in other words a set of any ...
249 views

### Where to find $\lambda$-calculus examples? For instance, how to check if a list is empty?

I'm trying to remove many layers of dust from my knowledge about $\lambda$-calculus, without my notes from classes (several hundreds of km and 5 years away). I was trying to understand the examples ...
723 views

### Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply ...
766 views

### Unable to construct Context-free Grammar from Pushdown Automaton

I have a problem in constructing a Context-free Grammar for the Language $$L = \{a^mb^n : m≠n,m>0,n>0\} .$$ Though I can able to construct a Pushdown Automata. I can construct a CFG, but it ...
the class $\mathfrak{F}_k$ of the fast growing hierarchy is the closure under substitution and limited recursion of the constant, sum,projections and $F_n$ functions for $n\leq k,$where $F_n$ is ...