gardenhead
  • Member for 7 years, 7 months
  • Last seen more than a week ago
  • New York, NY, United States
Uncomputability of Busy Beaver Function
4 votes

Here's a simple proof of the non-computability of the Busy Beaver function: Assume BB is computable. Then we can build a program that accepts a TM specification M and input x. Compute n = BB(|M|), ...

View answer
functional programming in terms of Set
1 votes

Generally, programming languages only make use of a single category - the category of all available types. If the type system is sufficiently simple, we may take that category to be Set; but usually ...

View answer
Does proofs are programs apply to any functional program?
0 votes

The Curry-Howard correspond is an observation that the structure of type systems mirrors the structure of logics, specifically propositions. Under this view, we can see similarities between an ...

View answer
How is algorithm complexity modeled for functional languages?
1 votes

Instead of formulating your complexity measure in terms of some underlying abstract machine, you can bake cost into the language definitions itself - this is called a Cost Dynamics. One attaches a ...

View answer
Calculating miss rates of word-addressable and direct-mapped cache
Accepted answer
4 votes

It seems you don't understand how cache lines work. A cache line is a contiguous chunk of memory. In this example, the cache line size is 32 bytes. This means that 32 contiguous bytes are always ...

View answer
how can a program be OS-dependent?
Accepted answer
1 votes

You're asking a different question in the body than the title. I'll answer the question "how can a program be OS-dependent?". There is no universal definition of an OS. At the very least you need a ...

View answer
How is a Transition System in Operational Semantics defined?
Accepted answer
2 votes

Operational semantics utilizes the tools of logic, so as a prerequisite we must understand judgements and inference rules. A judgement is like a proposition, but more general. It asserts a relation ...

View answer
How many bits for offset/frame/page
Accepted answer
1 votes

The frame size is 2KB. Assuming memory is byte-addressable, we need an offset into 2000 different bytes. 2000 is approximately (2^10)*2 = 2^11, so we need 11 bits for the frame offset. Then, we can ...

View answer
The difference between dense graph and sparse one
1 votes

You have to be careful with your definitions. For any graph, the number of nodes and the number of edges is a constant, so $O(V) = O(E) = (1)$. This is clearly not helpful. Sparse and dense only make ...

View answer
Language Features Not Translatable into Lambda Calculus
4 votes

That's not what "pure" means. Pure means, generally, that there is no mutable state, and no way to interact with the outside world (i.e. IO). Haskell is not "directly translatable" (what translation ...

View answer
Which of these simple data structures is most efficient when implementing a Dequeue?
Accepted answer
2 votes

We need to clearly separate interface interfaces (abstract data types) from implementation. You talk about implementing a deque, an ADT, in terms of a stack or queue, but those are themselves ADTs. We ...

View answer
Does CPU without register exist?
Accepted answer
4 votes

Theoretically, the answer to your question is a resounding "yes". A Turing Machine, the very first definition of computability in terms of machine models, has no registers. Neither do stack machines (...

View answer
Why multiple return values is not a common thing?
6 votes

Having multiple return values is preferable. Lacking them is bad design, plain and simple. However, we should clear up the misconception that such a thing even exists in the sense you are thinking of. ...

View answer
A question about type rule
4 votes

T1 is a schematic variable. Every consistent substitution of T1 with a type produces an instance of the rule. In a simple enough system, the inference rules can be used directly as the blueprint for a ...

View answer
Do the time and space complexities of a language depend on the Turing machine which is its recognizer?
2 votes

Yes, you are correct. I applaud your careful reading. This reading is most obvious if we view a TM as an algorithm (which they are). Clearly, for any computational problem, some algorithms are more ...

View answer
Compute equality comparison without comparison operators
0 votes

Since all arithmetic operations return an integer, and the result of an equality comparison must be a boolean, this is clearly impossible. Edit for updated question: This should do the trick in C: ...

View answer
Big O notation question for set insertion with sequential scan?
2 votes

First of all, let's get some things straight. Big-Oh notation is just a notation for describing the asymptotic behavior of any mathematical function (well, at least those defined on the real numbers). ...

View answer
Can someone give me an explanation of how dcaches works?
1 votes

what is considered a miss or hit and how this is calculated A hit occurs if the request word is in the cache; if not, we have a cache miss. It isn't clear how much you understand about hardware ...

View answer
Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n))
Accepted answer
1 votes

Let $d(n) = 2n$ and $e(n) = n$. Then $$d(n)-e(n) = n.$$ Since $d(n) = O(n)$ and $e(n) = O(n)$, we have that $$f(n) = g(n) = n,$$ so $$O(f(n)-g(n)) = O(n-n) = O(1),$$ and clearly $$n \neq O(1).$$

View answer
How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?
Accepted answer
2 votes

Your assertion that wait() and signal() are atomic is incorrect. The increment/decrement to s within the functions (s++, s--), are what's atomic. That being said, what you have given here is only one ...

View answer
Example for an unsatisfiable formula that can be made satisfiable by reordering quantifiers
3 votes

A very simple example is $$ \exists x \forall y (x > y) $$ where the universe is the natural numbers. If you want just literals (i.e. universe is booleans), then another example would be $$ \...

View answer
What exactly is computer science?
3 votes

"...asking myself daily when I would use these concepts in my daily life as a developer." The answer depends on the job. It sounds like you don't like math/theory, so you would not apply for/ get a ...

View answer
Finding hit ratio of a cache
1 votes

Since the line size is 8 words, 2 consecutive elements are loaded into the cache per miss. Now notice that each element is accessed twice, once for a read and once for a write. So for every even $i$th ...

View answer
generate possible inputs valid for automata
6 votes

Just do a BFS from the start state, and at every node keep track of what transitions you took to get there. Obviously this will only generate a finite number of words, as it doesn't follow cycles.

View answer
Is 2**x faster to compute than exp(x)?
7 votes

If by 2**x you mean $2^x$, then yes. We can use the left-shift operator <<, i.e. we compute 1 << x. This is lightning-fast as it is a primitive machine instruction in every processor I ...

View answer
Finding number not in list with wildcards
Accepted answer
7 votes

Reduce from SAT. Consider a CNF formula $\phi = C_1 \land C_2 \land \ldots \land C_m$ over a set of variables $\{x_i\}_{i=1}^n$. Construct an instance of your problem as follows: For each clause $C_i$...

View answer
Can a Boolean circuit be considered an algorithm?
1 votes

I don't think so, because when we think of algorithms (say as Turing machines), they allow the input to be any size. However, a family of circuits can $\mathcal C = \{C_n \ | \ n \in \mathbb N\}$, ...

View answer
Relationship between an NP-hard problems with the subsets of them?
-2 votes

Your question is worded very awkwardly, but I think what you're asking is "If we have a language $\mathcal L$ and we know there exists $\mathcal L' \subset \mathcal L$ such that $\mathcal L'$ is $NP$-...

View answer
How does an automaton model a computer or something else?
4 votes

What you seem to be talking about is a deterministic finite automata (DFA). A DFA has no output. It either accepts or doesn't accept its input. In other words, they only give yes/no answers. A Turing ...

View answer
Theory of computation introductory curriculum
Accepted answer
10 votes

Introduction to the Theory of Computation by Michael Sipser is a relatively recent entry into this field. It was the required book for a class my friend was taking, and I asked him for the PDF so I ...

View answer