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
24 views

Floating point numbers

In a certain computer represents numbers in base2, if the distance between 7 and the next largest floating-point number is $2^{-12}$. What is the distance between 70 and the next largest floating ...
0
votes
1answer
19 views

Primitive recursive function, constructing a proof

I've came upon an example in the book that is not that clear to me. The disparity function is proved to be primitive recursive in the following way: $$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(...
0
votes
0answers
29 views

Negative representation of a binary number

I saw online that if you want to convert a binary number to a negative binary number, you add 1.However, I don't understand why you do that.In a forum I saw someone explaining the following: ...
0
votes
1answer
40 views

A question about many-one reducibility of two sets

We want to show that $ \big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea. Would be grateful for your help.
0
votes
1answer
35 views

comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
0
votes
0answers
33 views

How to show that a function is primitive recursive?

If we have a function $g ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N}$ which is primitive-recursive. How to show that the function $f ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N} $ with $f(x_1, ~...~, ...
11
votes
4answers
1k views

How many bit strings of length 8 start with “1” or end with “01”?

A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have? I ...
0
votes
1answer
19 views

the set of extendable p.c. functions is not N

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$. Would be grateful for your help.
0
votes
1answer
33 views

Why This alternative way for retrieving the Original number from 2'S complement number works?

I was reading a book to learn about conversion from 2'S complement number to origianl binary number. During my past college study, I learened the following method for retrieving the Original number ...
0
votes
2answers
68 views

Turing Machine halts for at least $1024$ strings as input [closed]

Consider the language $$L = \{\text{"}M\text{"} \mid \text{Turing Machine } M \text{ halts for at least }1024\text{ input-strings}\}.$$ Is L a recursively enumerable language? My answer is no based ...
-1
votes
1answer
48 views

Iterate through integers solutions of linear inqualities [closed]

Say we have a set of integers value $x_1,\ldots x_n$ such that $$ \left\{ \begin{array}{l} a_{1,1} x_1 + \ldots a_{1,n}x_n \leq b_1 \\ \vdots \\ a_{m,1} x_1 + \ldots a_{m,n} x_n \leq b_m \\ x_1, \...
0
votes
1answer
54 views

Turing Machine & Recursively enumerable languages. [closed]

Suppose Turing Machine(TM) M and language L. L = { "M" | M has as input strings which $∈$ $\{0,1\}^{*}$ and terminate at a maximum of $512^{512}$ steps} Is L a recursively enumerable language?
2
votes
1answer
54 views

Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
0
votes
1answer
34 views

reductions from $SAT$ to $DSAT$ and $DSAT$ to $SAT$

can someone help me to prove or disprove the 3 claims about reductionsbetween $SAT$ and $DSAT$, where: $SAT=\{<\phi> | \text{$\phi$ is bolean formula in $CNF$ and there is an interpretation ...
0
votes
0answers
16 views

Prove that reverse of regular L is also regular [duplicate]

Prove that reverse of regular language is also regular. I know, how i can to this by using DFA of L. Changing directions of edges and so on. But how can it be done with Structural induction? What ...
-1
votes
1answer
56 views

Time complexity (in Θ –notation) in terms of n [closed]

I am struggling quite a bit trying to solve these and any help would be greatly appreciated. a) ...
0
votes
0answers
26 views

Given an array $A$ of length $N<10^6,$ how many subarrays have $\text{max}(A[x:y]) - \text{min}(A[x:y]) {\le} K$?

Given any K and an array of length $N$ what is the most efficient way to find the number of unique subarrays that satisfy this constraint? I believe there is an $O(N)$ solution using monotonic queues ...
0
votes
1answer
41 views

Not sure about Turing machine

Not quite sure, if I understand Turing machine correctly. So I tried building one, which should give back the predecessor of a number in binary code. e.g. 111 -Turing-> 110 picture of turing m. If ...
0
votes
2answers
54 views

Is there an way to calculate the value of O(n) [closed]

Is there an way to calculate the value of O(n) (Big Oh)? I understand it's use in algorithm. But my question is how is the value calculated?
0
votes
0answers
32 views

Modified version of SubsetSum

Let $L=\{(y_1,...,y_n,S,p)\ |\ \exists I\subset[n]\ s.t. \ |I|=p.\ \sum_{i\in I}y_i=S\}$. and $\forall\ 1\leq i\leq n\ :y_i \text{ is a positive integer}$, Assuming $\mathcal{P}\neq\mathcal{NP}$. ...
1
vote
1answer
30 views

What does it mean to say that an automaton construction is “effective”?

Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{...
2
votes
0answers
58 views

Counting divisions of an $n \times n$ grid [duplicate]

I'm looking for an efficient way to count the number of ways $D_n$ to divide an $n \times n$ grid into four (possibly empty) regions: top left, top right, bottom left and bottom right, such that no ...
3
votes
1answer
53 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
-1
votes
1answer
55 views

$L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
0
votes
0answers
14 views

Finding heavy independent sets

What are some good algorithms for finding maximum weight independent sets in a graph with vertex weights?
0
votes
0answers
21 views

Convert double precision number to rational fraction plus exponent

I have a double precision quantity (either pixels per cm or pixels per inch) that gets converted into pixels per meter. I then need to convert this number into a rational fraction, with numerator and ...
0
votes
1answer
35 views

Is the language regular

We have to check, if the given two languages are regular or not. L={w |each prefix of w has more 0 than 1} L'={w|w has a prefix with more 0 than 1}. I tried something like this: If L regular, ...
1
vote
1answer
32 views

NP problem that has a verifier that uses $\leq 3 \log_2 n$ bits of memory, how does that influence the complexity of the problem itself?

Translated exercise: Algorithms, that solve NP problems. Let's assume a problem $R$ is in the set $\sf NP$. A verifier $M(x,y)$ for this problem works in time $O(n)$ and uses extra information $...
1
vote
0answers
19 views

Is there a minimum spanning tree including $e$ after removing at most $k$ edges?

Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could ...
0
votes
1answer
21 views

How to efficiently sample $y$ in intervals of $\Delta x$ in an “ascending” cubic Bézier curve?

For a cubic Bézier curve defined by control points $\boldsymbol{P_0}$, $\boldsymbol{P_1}$, $\boldsymbol{P_2}$ and $\boldsymbol{P_3}$ with the formula $\boldsymbol{B}(t) = (1 - t)^3\boldsymbol{P_0} + ...
0
votes
0answers
21 views

Red-black tree insert

I'm currently trying to figure out this exercise (sorry for link to image, it's for the red-black trees): http://i.imgur.com/IKMCkVf.png And I do know that the correct one is number three from the ...
1
vote
1answer
22 views

For formal languages $U,V \subseteq X^{\ast}$, what is $\min(U\cdot V)$

Let $L$ be some language, and consider the operator $$ \min(L) := \{ u \in L \mid \mbox{no proper prefix of $u$ is in $L$} \} $$ where a word $u$ is called a prefix of $w$ if it is an initial segment ...
0
votes
1answer
23 views

Max Flow Min Cut - Prove that $e$ crosses some minimal cut

I already asked about the opposite direction but I'm really confused about it, so I'd like to get some help please: Let's assume we have a flow network $G$ and some edge $e$. Now, Let's assume ...
1
vote
2answers
14 views

Max Flow Minimum Cut - after removing an edge

Suppose that the max flow of a network is $|f|$ and there's a minimum-cut $(S,T)$ such that $e$ is an edge which crosses the cut. Why is it must be that the max flow after removing $e$ is exactly $|...
1
vote
1answer
38 views

Although proven by pumping lemma language is not regular [closed]

We have to show, that although the language $L=\left\{qw^jq^k \mid j,k \in \mathbb N, j>k \mbox{ or }j \mbox{ is not even }\right\}$ satisfies pumping lemma, it is not regular. Okay, my try: For $...
0
votes
1answer
37 views

Undestanding SVM

I am the moment trying to understand how SVM works.. I understand the concept of finding a seperating hyperplane with the highest margin, but i do not understand how it works in mathmatically. Mor ...
0
votes
1answer
28 views

What are “definable integer sequences”

According to Wikipedia, An integer sequence is a definable sequence, if there exists some statement P(x) which is true for that integer sequence x and false for all other integer sequences. ...
0
votes
1answer
28 views

proving not regular with pumping lemma

Not quite sure if I understand pumping lemma correctly. so if i have this language and i like to show it is not regular: L={ $q^a w^be^c| a,b,c \in N, a+b=c$}. If L would be regular, than there ...
1
vote
1answer
36 views

A Question about Computable Functions

Barry Copper states following in his Computability theory book which I have a question about them. Exe.4.5.1: Show that if $\varphi_e(x) \downarrow $ is a computable relation, then so is ...
2
votes
1answer
98 views

Are sets and symbols the building blocks of mathematics?

A formal language is defined as a set of strings of symbols. I want to know that if "symbol" is a primitive notion in mathematics i.e we don't define what a symbol is. If it is the case that in ...
0
votes
1answer
34 views

Determine whether a language belong to R,RE\R,coRE\R or other

For the following language, determine to which class it belongs $$L_3=\left\{\langle M\rangle\Big\vert|\langle M\rangle|\le 2016\text{ and M is a TM that accepts }\varepsilon \right\}$$ I've ...
0
votes
0answers
61 views

Having rand2() function build rand5()

I was asked this question long time ago. Having a function $rand2()$ (in any computer language, "rand" means random) which returns $0$ or $1$ (two values only) with a uniform distribution, i.e. $$P(...
0
votes
0answers
30 views

What is computational complexity of a coding technique

In my previous Question Help in understanding a coding technique based on inverse mapping of a dynamical system I learnt how to apply chaotic map in coding theory in communications. Steps: (1) The ...
2
votes
0answers
24 views

Modal extensions (operators) for monoidal (categorical) logics

There is nice generalization of first order logic to monoidal (categorical) logics http://www.springer.com/us/book/9783642128202 which has recently been applied extensively as replacement for deontic ...
0
votes
0answers
28 views

Are these functions computable - Understanding computable functions

There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...
0
votes
0answers
20 views

How do I calculate such possible number of total and serial schedule?

Consider the following two transactions $T_1$ and $T_2:$ How many non serial schedules are possible, if we execute both transactions concurrently? $3000$ $3001$ $3002$ $3003$ My try: ...
-3
votes
1answer
26 views

Deterministic Turing Machines

Let's say that M is a deterministic Turing Machine, can I say that for a certain input I will have the same output? How can I demonstarte this?
0
votes
0answers
45 views

Construction of Permutation Group (bounded order) from a Set of Permutation

Given a set of permutation $S$. It has $|S|$ (The cardinality of $S$) elements. Consider a subset $A\subset S$. We can construct a group using $A$. One possible algorithm could be- We start ...
1
vote
1answer
48 views

Prove that if $xy=yz$ then $ \exists u,v \in A^*$ and $\exists p \in\mathbb N$ such that $x=uv$, $z=vu$ and $y=(uv)^pu$

Prove that if $xy=yz$ then $ \exists u,v \in A^*$ and $\exists p \in \mathbb{N} $ such that $x=uv$, $z=vu$ and $y=(uv)^pu$. $A^*$ is the set of all words that can be formed over the alphabet $A$. By $...
0
votes
1answer
17 views

Grammar generator for the Knight (Chess)

I'm trying to build a regular grammar to generate the valid movements for the knight. I'm using (U)p, (D)own, (L)eft, (R)ight to represent each of the components of the movement. I already have a NFA ...