• Member for 7 years, 7 months
• Last seen more than a week ago
• New York, NY, United States

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|), ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 (...

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. ...

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 ...

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 ...

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: ...

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). ...

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 ...

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).$$

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 ...

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  \...

"...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 ...

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 ...

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.

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 ...

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$...

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\}$, ...

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$-...