# Questions tagged [computer-science]

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 questions from scientific computing, use (computational-mathematics).

5,149 questions
Filter by
Sorted by
Tagged with
38 views

### What is the cardinality of the set of all binary trees defined over the natural numbers?

I've been wondering what the cardinality of all binary trees would be? Let me define binary trees to be clear. I am using an inductive definition : The set $B(\mathbb{N})$ of binary trees over the ...
45 views

### Doubt in Paper on Algebraic topology and Concurrency

I am trying to read a paper on Algebraic Topology and Concurrency (doi: 10.1016/j.tcs.2006.03.022), which claims to make use of Dijkstra's notation in talking about concurrency. Specifically, I am ...
14 views

### How can I create an Arc path from 3 point (p1-->p2-->p3) in 3D space?

I want to create an Arc path over 3 points in 3D space. I decided to draw a circle over them and then extract sector from p1 to p3 that passes through P2. I use this code but it did not extract sector ...
40 views

### Halting problem reduction, what am i doing wrong

I have the following problem. Prove that $L_1=\{\langle M\rangle| \exists w \in \Sigma^*: M(w)\downarrow\}$ is undecidable (where $M(w) \downarrow$ means M halts on input w). I have come up with this ...
95 views

### Good Algorithm to Compute all Subgroups of a Finite Group.

Let's suppose we have a group $G$ of finite order $n$. We want to algorithmically compute all subgroups, and there are some ways to do that. First one: Compute all subsets. Verify for each of them if ...
59 views

### Struggling with how to solve Proof by Induction [closed]

If we formally define the length function $f(w)$ of a string $w=w_1w_2\cdots w_n$ (where $n\in \mathbb{N}$ and $\forall i=1,\ldots ,n$, $w_i\in \Sigma$) as if $w=\varepsilon$, then $f(w)=0$. if $w=au$...
43 views

### A confusion on $\beta\eta$-reduction

Recently I've started exploring lambda calculus, and currently I'm tackling the next exercise: Prove that if $M =_{\beta\eta} N$, then $FV(M) = FV(N)$, Where $FV(P)$ stands for free variables in the ...
22 views

### Difficulty understanding a 1-tape TM program which solves and includes time analysis of the program [closed]

I need to sketch a 1-tape TM program which solves and also includes a time analysis of the program, e.g. 𝑂(𝑛), 𝑂(𝑛𝑙og 𝑛), 𝑂(𝑛3), etc.; 𝐿 = {𝑢#𝑣: 𝑢, 𝑣 ∈ {0,1}∗ and 𝑢 is a substring of 𝑣}
1 vote
43 views

### The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

I saw this pseudocode from the book Introduction to algorithm (Chapter 31 page 957) on how to implement Modular Exponentiation. ...
251 views

### Why do greedy coloring algorithms mess up?

It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are ...
46 views