Problem Detail: Let $Sigma = {0,1}$. For every word $w in Sigma^*$, let $|w|_0$ and $|w|_1$ denote the count of 0’s and 1’s, respectively, in $w$. Let $L$ be the language $$L = { w in Sigma^* mid |w|_0 gt |w|_1 Read More …
Blog
[Solved]: Why would you use a monitor instead of a semaphore?
Problem Detail: I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do not understand why I would use a Read More …
[Solved]: Why is automated theorem proving impossible?
Problem Detail: As far I know, in general case there is no Turing machine which could get any theorem on its input and produce its proof on its output. Why is it so? Asked By : peterh Answered By : Jake We have Read More …
[Solved]: Formal notion of a call graph for Turing machines
Problem Detail: To most computer programs one can assign a “call graph“. Is there a formal notion of call graphs of Turing machines? Motivation is, that one could intuitively call a decidable language $L$ “irreducible” if every Turing machine which decides Read More …
[Solved]: Is {ww^r ww^r} a context-free language?
Problem Detail: Is the language $L = {w w^r w w^r mid w in Sigma^*}$ context-free? ($w^r$ is the reversal of $w$.) I heard that by using the pumping lemma, we can only prove that a language is not context-free, but Read More …
[Solved]: The control in the Turing Machine
Problem Detail: My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on Read More …
[Solved]: Showing that tournament sort requrires O(n log n) comparisons
Problem Detail: I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has Read More …
[Solved]: Counting the number of N-dimensional coprime integer vectors
Problem Detail: I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors. The vectors in my set are $N$-dimensional integer vectors whose components are bounded on the top Read More …
[Solved]: How to random-generate a graph with Pareto-Lognormal degree nodes?
Problem Detail: I have read that the degree of nodes in a “knowledge” graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution. Where can I find a kind of algorithm that Read More …
[Solved]: The “CPS” approach has done great harm to performance in SML/NJ; reasoning desired
Problem Detail: In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated: Note that the “CPS” approach has done great harm to performance in SML/NJ. Its physical evaluation Read More …
