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

0
votes
0answers
14 views

Phython code to construct the stone-cech compactification for a non-compact space.

This is a big project. Anyone interested in this? Let us work on it together. First is it a project that is acheivable?
0
votes
0answers
17 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 ...
-6
votes
2answers
58 views

Inverting surjective functions as proof that P≠NP [on hold]

I am attempting to show that P≠NP by inverting surjective functions. My proof is below, is there anything invalid with this proof?
0
votes
0answers
11 views

Classify $\{ \langle M \rangle |M \text{ is a turing machine so } L(M) \leq_M A_{TM} \}$

Let $$L = \{ \langle M \rangle |M \text{ is a turing machine so } L(M) \leq_M A_{TM} \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{RE} ...
1
vote
1answer
44 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
16 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 ...
-2
votes
0answers
28 views

Finding recurrence relations in terms of n

The runtime of orange is log (n) and the algorithm is as follow ...
-2
votes
0answers
21 views

What is phase transition in 3-SAT [on hold]

I understand the basic concept of 3SAT. Can anyone explain about what is phase transition in 3-SAT? As simple as possible. I tried google but the result come out which is far from what I understand ...
1
vote
2answers
27 views

equivalent regular expr

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it. Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for ...
2
votes
1answer
82 views

Is [a, a[ empty?

Is the segment $[a, a[$ equivalent to the point $\{a\}$ or the empty set $\varnothing$? Can one or other be formally proved? I was wondering because in computer science it is the empty set, as the ...
0
votes
1answer
45 views

b tree least upper bound

Hi I have an university assignment question that I can't fully understand. My tutor doesn't understand some of the terminology and my lecturer in the subject is not particularly forthcoming. The ...
0
votes
1answer
13 views

Is there a Relationship Between Multi-Valued Logic and n-Satisfiability?

Is binary (Boolean) logic related at all to the two-satisfiability problem? And is ternary logic related in some way to the three-satisfiability problem? Would it follow then that if one were to ...
2
votes
0answers
42 views

In a directed graph with $n \geq 2$ nodes, if two different nodes reaches $n$ nodes, then this graph has a directed cycle.

I think this statement is true because if first node can reaches every other node (including second node) and second node can reaches every other nodes (including first node), then first node and ...
1
vote
0answers
20 views

Rightmost derivation word aaaccb

I have got these context free grammar: $S \implies aSA | a \\A \implies Ab|c$ The goal is find rightmost derivation of word $aaaccb$ a draw derivate tree, which corresponding with this derivation. ...
0
votes
1answer
20 views

Context-free grammar and regular expression

I have got these Context-free grammar/regular expression: (1) $abba^{*}$ (2) $abb(a+b)^{*}$ (3) $a^{*}ba^{*}ba^{*}$ (4) $S \implies abA \\ A \implies Aa|b$ (5) $S \implies aS|bA \\ A \implies ...
0
votes
1answer
21 views

Is every decidable language accepted by a turing machine? [closed]

I am taking a cs class and the lecture slides are not very complete on this topic. can somebody clarify? thank you
2
votes
3answers
37 views

Naming binary strings

Given a string of 1's and 0's, containing the same number of 1's as 0's, is there a way to uniquely "name" each string with a number such that it is computationally easy to go between this "name" and ...
1
vote
0answers
50 views

How Do You Write Mathematical Proofs | Linear Algebra (I have no idea what I am doing…) [closed]

I am a Computer Science student, and right now I am taking a 15 week Summer class on Linear Algebra. This course will cover proof writing (basic) and I have never written a proof like these in my ...
1
vote
0answers
21 views

Discrete Mathematics: Prove Expression Is Even

I'm brushing up for my Discrete Math final exam, and would like to know if the following proof is valid... Prove by direct proof that $a^2-5a+8$ is even for any integer $a$. Proof: By ...
2
votes
1answer
31 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
0
votes
1answer
18 views

Number system question

Is it true that if we are given a number system with base 3, mantissa 2, $-1 \le p \le 1$, determined by $$\pm 0.d_1 d_2 \times 3^p$$ where each number is normalized, unless it is zero, then the ...
2
votes
1answer
48 views

Longest Common Prefix among $n$ strings with length $k$

Suppose I have a set of alphabet $\Sigma = \{ A,B,\ldots,Z \}$ with $|\Sigma|=26$. I am generating a set of $n$ random strings $S$, with each string of length $k$ from the alphabet (for the random ...
0
votes
0answers
25 views

Discretizations of Differential, Geometric and Topological Notions

I have noticed a recurring theme in Graph Theory / Theoretical Computer Science (abbreviated GT and TCS throughout this post) in that notions typically belonging to differential calculus / geometry / ...
1
vote
0answers
60 views

What is the relationship between Realizability and the Curry-Howard isomorphism?

I have recently been studying the Curry-Howard isomorphism/correspondence. My sources have primarly been Sørensen [1] and Girard [2]. Realizability is introduced here in the form of Kleene's ...
1
vote
1answer
23 views

Showing equivalence of 2 Big O notations

I have the task to show that the following two big O definitions are equivalent. My first thought was that it has to be equivalent because the set of natural numbers excludes all broken rational ...
0
votes
1answer
15 views

Demonstrate that a language is semi-decidable

I need some help to demonstrate that this set below is decidable, semi-decidable, or undecidable. Here's the set: H = {p| |Images(fp)| >= 10} explanation: an ...
0
votes
0answers
14 views

Show how to construct new AKE protocol

I'd appreciate if someone could help me with this exercise (image is for text and notation): http://i.imgur.com/S6xmkEX.png Could someone give me a hint, what am I supposed to do to show it?
1
vote
0answers
32 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
0
votes
3answers
34 views

What does the algorithm s = s + k * k do?

I just finished an exam in my math class and I did well except for one question that I just can't get out of my head, it seems simple but I just can't figure it out: PROBLEM: ...
2
votes
0answers
19 views

levenshtein distance: iterative vs single calculation

I had a list of 1100 words and sought to cluster them based on a levenshtein distance of 2. This reduced the list to 900 words. Running the calculation again reduced the number to roughly 800, and ...
0
votes
1answer
28 views

Solve $T(n)=2T(n/2)+\log n$ with $T(1)=1$

Solve$$\begin{cases}T(n)=2T(n/2)+\log n\\ T(1)=1\end{cases}$$ I tried to use the master theorem but it didn't work, so I used the trees methode ...
0
votes
0answers
24 views

Algorithm to find password from hash value

I'm currently trying to solve this exercise (sorry for link to image, but there's a bit text): http://i.imgur.com/ETaCK0H.png But there's a few things in the exercise I don't understand. For ...
8
votes
1answer
352 views

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
-2
votes
0answers
56 views

What are the Correct Conditions for Akra-Bazzi Master Theorem?

The Akra-Bazzi method solves recurrences of the form: $$T(n) = g(n) + \sum\limits_{i=1}^k a_iT(b_in + h_i(n))$$ In the Wikipedia article about the topic, it says that the condition on $g(n)$ is: ...
0
votes
2answers
41 views

Bit increase when averaging?

I have a given number $N$ of binary numbers, that are stored using a given number $B$ of bits. $B$ is the same for all the numbers. For example, thease values where $N = 4, B = 4$. ...
12
votes
1answer
270 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
2
votes
0answers
16 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
0answers
42 views

Arc length using bisection error - root finding methods.

Apologies if this is poorly formatted - it is my first time posting a question. I'm trying to find evenly spaced arc lengths along a function (in this case a sinusoid) using the bisection method. ...
1
vote
1answer
21 views

Hilberts tenth problem over $\mathbb R$ with coefficients in $\mathbb Q$

Consider the following decision problem: Given: An equation $f(x_1, \dots, x_n) = 0$ where $f(x_1, \dots, x_n)$ is a polynomial with variables $x_1, \dots, x_n$ and coefficients in $\mathbb Z$. To ...
1
vote
2answers
31 views

Find particular pair of values that satisfy equation

I think this is might be a fairly simple problem, but I can't for the life of me think of a way to approach it. In this equation, for a given $x$ and $y$, with $x,y,a,b$ non-negative integers: $x2^a ...
0
votes
1answer
33 views

Course or book - Math Foundations in CS

I want to improve my math skills, now I'm trying to find good route for this purpose. I'm using Khan Academy, and recently found "CS103 - Mathematical Foundations of Computing" course which looks good ...
1
vote
1answer
44 views

What formal systems are various programming paradigms based on?

I heard that functional programming paradigm is based on lambda calculus and combinatory logic. If I am correct, lambda calculus and combinatory logic are formal systems. What formal systems are ...
0
votes
1answer
46 views

Solve $T(n)=16T(n/2)+2n^4$

Solve using the iteration method: $$T(n)=16T(n/2)+2n^4$$ My attempt: $$\begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ ...
1
vote
0answers
24 views

ternary string that contains only $0's$, $1's$, and $2's$

A string that contains only $0's$, $1's$, and $2's$ is called a ternary string. (a) Find a recurrence relation for the number of ternary strings that do not contain two consecutive $0's$. (b) What ...
0
votes
0answers
21 views

What does “symbolic computation” mean in this context?

From Wikipedia In computational mathematics, computer algebra, also called symbolic computation or algebraic computation is a scientific area that refers to the study and development of algorithms ...
1
vote
0answers
32 views

What is the root of first class object in programming languages?

What is the root of "first class object" of programming languages? (Also see https://en.wikipedia.org/wiki/First-class_function, and ...
0
votes
0answers
20 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) ...
-1
votes
1answer
37 views

If NP-complete, prove another is also NP-complete

I've been trying to work on this problem but I don't really know where to start and can't find any resources online. Would it be possible for someone to guide me through step by step.
0
votes
0answers
12 views

Minimum number of pages in a B-Tree of order n?

How can I calculate the minimum number of pages in a B tree of order n and height 3? 1st level = 1 page 2nd level = 2n+1 pages 3rd level = ? 3rd level is 1? Or how many pages?