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

learn more… | top users | synonyms

1
vote
1answer
117 views

Difference between language is decidable and function calculable by turing machine

I'm trying to understand the difference between saying a language is decidable and a function is calculable by a turing machine. I must have understood something wrong, because for me it doesn't make ...
1
vote
1answer
196 views

Euclidean Division to avoid need for floating point arithmetic

In simple terms (that Google has been unable to provide the answer), is there an approach to dividing a whole integer by a quotient & remainder? As a specific example, ...
-2
votes
1answer
90 views

Limiting search space for efficient line matching [closed]

I have 2D line segments extracted from an image. So i know end point coordinates of them. also, i have some reference 2d line segments. Both line segments are now in vector form. comparing to ...
1
vote
1answer
222 views

Ackermann function in terms of higher order recursion

Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition \begin{equation*} A(m,n)=\left\{ \begin{array}{ll} n+1 & \text{if $m=0$} \\ A(m-1,...
1
vote
1answer
1k views

How do I find the number of bit strings with 3 consecutive 0s in a bit string of length n?

Say n is 8. How would I ever solve this problem? I've Googled around and searched this site but I haven't come up with much. I'm not even looking for the answer necessarily, just the process by ...
0
votes
3answers
912 views

Are these languages context free or not?

$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* \...
1
vote
1answer
403 views

Minimum number of moves to create a new permutation

Edit: Before you begin, please note that a move refers to swapping a pair of letters (thanks to ferfer93) Ok, so I understand the title is a bit ambiguous, so I'll clarify it further below: Let us ...
1
vote
0answers
118 views

Question regarding implicant chart of Quine-McCluskey algorithm

In https://en.wikipedia.org/wiki/Quine-McCluskey#Example, at the end of Step 1, there is a table that shows the number of 1's, minterms, 0-cube and size-2 implicants and size-4 implicants. But I am ...
2
votes
1answer
154 views

The existing bound on Edmonds-Karp doesn't seem to be tight

(I have posted the following in theoretical CS stackexchange, but realized that it's the wrong place, so I'm reposting it here) I'm reading CLRS's (Cormen et.a al) Introduction to Algorithm, and ...
1
vote
3answers
3k views

Way of simplifying binary multiplication

Is there a way to simplify multiplication of binary numbers regardless of digits? Or do we always have to resort to 10-base multiplication? As computers do multiplication, there should be ways to ...
1
vote
1answer
118 views

Space : Kolmogorov complexity :: time and space : ___?

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
3
votes
1answer
379 views

Why is $ab+bc+ac = 0$ in some situation?

This is originally a Computer Science question, but I ran a equation that is too hard to solve. Here goes. So the problem is quite simple, given positive integers $a$, $b$, $c$, and calculate $\sqrt{...
4
votes
1answer
168 views

Prove that all combinators must fulfill A x = x for some x, given that M x = x x and composability of any two combinators

I'm working through Raymond Smullyan's "To Mock a Mockingbird" and I'm stuck on the first problem in the combinatory logic section. I'd appreciate hints, but no spoilers please. The problem is ...
3
votes
2answers
139 views

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags?

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags ? Let me rephrase the question by example, we have a set T{O,...
1
vote
2answers
201 views

Is there a limit to how exact $\pi$ can be calculated? [duplicate]

Possible Duplicate: Do We Need the Digits of $\pi$? Working out digits of Pi. What are the limitations? Faster computers More accurate measuring devices
0
votes
1answer
149 views

Regular grammar and context grammar problems

If $G$ is not a regular grammar, then $L(G)$ is infinte. If $L^*$ is context free then $L$ is definitely context free. If $G$ is a context free grammar that is language is $L$ (meaning $L(G) = L$), ...
1
vote
1answer
316 views

Programming related calculus & math symbols and questions

I am reading a textbook for my next semester just for fun. I didn't study so hard during the high school so I have missed out many vital information. Questions: 1) What is λ -calculus and λ (in ...
1
vote
1answer
110 views

Proving uncomputability — Rice's theorem

I am trying to prove the uncomputability of the following function: Let $\varphi$ be a Gödel-numbering of the computable functions. Consider the following function: \begin{align*} f(x) = \left\{ \...
1
vote
0answers
68 views

Regression with multiple line types from set of points

Given a set of points, I'm looking to find the best possible line (within reason) to fit to these points. These points won't be from real data, so they could form any sort of curve or line. So, I ...
3
votes
2answers
221 views

Primitive recursive select from parameters

I'm looking forward function, that works like that $\mathbb{N}^{n+1} \rightarrow \mathbb N$: $f(y, x_1, x_2, \dots ,x_n)=x_y$ We use projection $\Pi^n_k$, but I need something with "dynamic" size ...
3
votes
1answer
364 views

Steps in the Simplex Method

I'm trying to look at how the Simplex method in standard form works. I understand the basics of how ti works, but I can't understand what happens between two steps. I'm using the example from chapter ...
1
vote
0answers
103 views

Asymptotic analysis for multiple variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
0
votes
2answers
71 views

Asymptotic constants for a quadratic?

Note than $n$ is a parameter for the functions. For some constants $c_1, c_2$ and $n_0,$$$c_1n^2\le an^2 + bn + c \le c_2n^2$$ for all n > $n_0$. Consider any quadratic function $f(n) =an^2 +...
1
vote
0answers
221 views

PDA state diagram with an inifinite languge but with no looping states

For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the ...
0
votes
1answer
1k views

How to prove perm-power is in P?

Let $\mathit{PERM\text{-}POWER} = \{ \langle p, q, t\rangle \mid p = q^t \}$ where $p$ and $q$ are permutations on $\{1, \ldots, k\}$ and $t$ is a binary integer. How do I prove that $\mathit{PERM\...
0
votes
2answers
108 views

Is the halting of a program that checks for duplicates in an infinite multiset decidable?

A program $P(\Sigma)$ takes input $\Sigma$, which is an nonempty multiset. Let $\Phi$ be an empty multiset. Take any element $\sigma$ from $\Sigma$. If $\sigma \in \Phi$, return true. Otherwise, ...
1
vote
4answers
88 views

Procedures to find solution to $a_1x_1+\cdots+a_nx_n = 0$

Suppose that $x_1, \dots,x_n$ are given as an input. Then we want to find $a_1,\ldots,a_n$ that satisfy $a_1x_1 + a_2x_2+a_3x_3 + a_4x_4+\cdots +a_nx_n =0$. (including the case where such $a$ set does ...
-1
votes
1answer
265 views

How to show if a function is partial recursive?

I have seen and understood the most definitions but i just could not understand how to show if a function is mu-partial recursive or not. I used search engines, but all I find are just more lectures ...
0
votes
1answer
653 views

machine numbers in IEEE single precision

Is the following numbers machines numbers on the IEEE single precision system? $10^{304}$ $2^4+2^{27}.$ What do I have to do to know whether they are machine numbers on IEEE single precision?
1
vote
1answer
199 views

The set of Turing machines that recognize $\{00, 01\}$ is undecidable

$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable. I am really having difficulties even understanding the reduction to use here....
7
votes
1answer
1k views

Why can't reachability be expressed in first order logic?

I'm wondering why we can't express graph reachability in first order logic in pretty much exactly the same way we express it in second order existential logic. For SOL, one definition is : 1 . L is ...
0
votes
1answer
115 views

Why do we need tactics, reflection and other techniques when we have Curry-Howard for theorem proving?

First of all, I apologize if this question is slightly misplaced, but this seemed the best place to ask it given the mathematical/theoretical nature of the discussion. Given that the Curry-Howard ...
1
vote
1answer
219 views

Depth first search on graph

I have a homework problem I think I know the answer to, but want to double check Consider the graph with three nodes, $a$, $b$, and $c$, and the two arcs $a \rightarrow b$ and $b \rightarrow c$. ...
1
vote
1answer
468 views

Reduction to prove that the function is not computable

Use reduction to show that the following function is not computable, where P is any python program that takes a single input x: sotrue(P) = true, if P(x) returns true for every value of x, sotrue(P)...
2
votes
1answer
249 views

Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question Prove, by induction on k, that a connected component of k nodes ...
0
votes
1answer
53 views

Parallel computing : scheduling processors for large sums

does anyone know if there exists in the literature an algorithm that solves the following problem? I have M different and indipendent sums, and P processors. The size of sums are in ascending order ...
6
votes
2answers
576 views

Big Oh notation of $7x^2$, confused

I'm supposed to figure out the Big-Oh notation of $7x^2$. Take a look at this. Now this says: Show that $7x^2$ is $O(x^3)$ When $x>7, 7x^2<x^3$, So let $C=1$ and $k=7$, we see $7x^2$ is $...
1
vote
1answer
96 views

Diagonal of a convex polygon such that the obtained cuts have simmilar areas

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem Problem. Find in linear time a diagonal of $P$ such that the absolute ...
1
vote
1answer
82 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...
2
votes
1answer
171 views

LTL translation to omega-regular languages

I tried to define a translation from LTL to ω-regular languages. I built it inductively on the structure of LTL formulae. No problem except with the 'until' operator where I came up with the ...
0
votes
1answer
6k views

Introduction to the Theory of Computation Solution Manual - Michael Sipser

I am hoping to test out a Theory of Computation class for next semester and have bought the course's textbook, Introduction to the Theory of Computation by Michael Sipser to prepare. I was trying to ...
4
votes
2answers
89 views

Finding N elements that are included in as many sets as possible

Say I have 20 sets, containing a variable amount of elements. How would I go about finding the 10 elements that cover the most number of sets? Imagine I could search for three terms at once on ...
0
votes
2answers
133 views

floating point binary arithmetic

Prove that the decimal number $\displaystyle \frac{1}{5}$ cannot be represented by a finite expansion in the binary system.
1
vote
2answers
416 views

Finite representation in the binary $\implies$ finite representation in the decimal system

Any number that has a finite representation in the binary system have a finite representation in the decimal system. Why?
1
vote
1answer
241 views

Floating point arithmetic

How can I prove that : a real number has a finite representation in the binary system if and only if it is of the form $$\pm \frac{m}{2^n}$$ where n and m are positive integers.
1
vote
0answers
440 views

Diffie-Hellman key exchange public key calculation

I encountered a question that I can't seem to get around it. Lets say user A and B uses the DHKE defined over $GF(2^8)$ induced by the irreducible polynomial $x^8 + x^4 + x^3 + x^2 + 1$ and the ...
8
votes
6answers
10k views

Great Book on Probability and Statistics (for Computer Scientists)

I'm a Computer Science sophomore and we're studying Probability and Statistics (fundamentals and all). The teacher recommends a book which I don't like since it does not even try and explain ...
0
votes
0answers
65 views

is it possible to reduce the weight of a best fit line (least squares) given new data points?

I have a simple best-fit-line algorithm similar to this description. Without memorizing the points history, it is easy to calculate a rolling best fit line as long as we remember (store) the ...
7
votes
2answers
1k views

Finding the 2,147,483,647th prime number

In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a ...
1
vote
0answers
244 views

Power sums, fast algorithm

I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm ...