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.

learn more… | top users | synonyms

0
votes
1answer
79 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.
0
votes
2answers
222 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 ...
2
votes
1answer
705 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 ...
2
votes
3answers
453 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$ ...
4
votes
1answer
427 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 ...
1
vote
1answer
1k 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 ...
3
votes
1answer
285 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, ...
5
votes
2answers
4k 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 ...
2
votes
1answer
315 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 ...
0
votes
1answer
114 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 ...
0
votes
2answers
416 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 ...
0
votes
1answer
83 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 ...
1
vote
1answer
84 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 ...
9
votes
2answers
1k 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 ...
1
vote
0answers
117 views
17
votes
2answers
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 ...
4
votes
1answer
68 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 ...
2
votes
1answer
354 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 ...
1
vote
2answers
144 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 ...
13
votes
1answer
1k 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 ...
1
vote
0answers
467 views

Regular expression from DFA

I want to create a regular expression from the following deterministic finite automaton using an equivalence system: $\begin{align}L_1 = & \{a\}L_1 &\cup& \{b\} L_2 & \cup & ...
3
votes
1answer
62 views

Equivalences of regular expressions - which one is wrong?

Let $\alpha,\beta \in \text{RA}(\left\{0\right\})$ where $RA(\Sigma)$ is the set of all regular expressions of the alphabet $\Sigma$. The following two equivalences are given: ...
1
vote
1answer
130 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 ...
22
votes
1answer
608 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 ...
0
votes
2answers
102 views

What (formal) language does this describe? And, how do I prove it's regular?

I have this problem that I can't seem to be able to wrap my head around, and I was wondering if there was someone here that could help me understand it. Let $L_1$ be a regular language over $\{a, b, ...
2
votes
2answers
348 views

Time complexity of sorting a partially sorted list

Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order. How would you sort the whole list given the following: a) $f(n)=O(1)$ b) $f(n)=O(\log n)$ c) $f(n)=O(n^{1/2})$ d) ...
3
votes
1answer
144 views

How to intercept someone moving in a 2-dimensional grid world?

Suppose you have a discrete 2D grid where each point represents a person, for example $\mathbf{d} = (x_d, y_d)$. Each person can only move exactly one square up, left, right or down (or stay put) per ...
0
votes
1answer
173 views

inverse polynomial

I am reading from some notes on cryptography and came across this sentence: "We call a function f negligible in k if it asymptotically approaches zero faster than any inverse polynomial in k i.e., ...
0
votes
1answer
259 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?
3
votes
1answer
369 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 ...
2
votes
1answer
205 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 ...
6
votes
1answer
619 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 ...
3
votes
2answers
885 views

Advice for how to learn more advanced math for audio signal processing?

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 ...
1
vote
2answers
257 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 ...
1
vote
1answer
585 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 ...
2
votes
4answers
131 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 ...
2
votes
1answer
209 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 ...
3
votes
1answer
388 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 ...
2
votes
1answer
622 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 ...
2
votes
3answers
188 views

Math/CS Algorithm Analysis Question

I've placed this on the Math Stack Exchange even though it is really a CS question because it is the math that is stumping me. Please note, I'm not asking you to do this problem for me, just to make ...
1
vote
1answer
183 views

which class does this function belong to in the fast growing hierarchy?

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 ...
3
votes
2answers
294 views

Formally verifying that $n \log n = o(n^2)$

I am trying to verify that $n \log n = o(n^2)$ using the formal definition of small-o. The definition of small-o is as follows Let $f$ and $g$ be functions $f,g: \mathbb{N} \rightarrow \mathbb ...
5
votes
2answers
356 views

Regular Expression question

Notepad++ has a "regular expression" search but it does not implement the pipe OR | operator, which allows you to take two regular expressions and union them into ...
12
votes
4answers
5k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
1
vote
1answer
209 views

About a ordinal-based definition of fast-growing functions

I try to understand the Löb-Wainer-hierarchy and one definition just doesn't open. I hope someone could clarify this to me. A fundamental sequence to limit ordinal $\alpha$ is $\omega$-sequence ...
1
vote
1answer
239 views

Optimizing a string to have the shortest possible unique substrings

I would like to construct a length $N$ string over a $k$-letter alphabet, $S$, such that any substring of $P$ sequential characters in $S$ is unique for as small a value of $P$ as possible. To ...
0
votes
2answers
224 views

Bell number calculation [closed]

Sorry if this forum is not relevant for programming question, but please if possible help me. I have the following code to calculate the Bell number: ...
2
votes
0answers
183 views

Further question on “uncountable” Turing Machine

Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
5
votes
2answers
575 views

How to determine if it's possible to draw a graph $G$ with a given set of vertices?

Given a list of vertices associated with its degree, says: $$7, 7, 3, 3, 3, 3, 3, 1$$ Determine whether it is possible to draw a graph $G$, where $G$ is connected and un-directed. Solution: ...
13
votes
3answers
443 views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what ...