Skip to main content
Share Your Experience: Take the 2024 Developer Survey
15 votes

Does there exist an equivalent arithmetic circuit for each computable function?

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate ...
D.W.'s user avatar
  • 161k
12 votes
Accepted

Does every turing machine have an equivalent, single-state, n-tape turing machine?

Yes, there always exists a machine, and we really only need 2 tapes. Your standard TM transition might be written: $\delta(S_n, a) = (S_m, b, r)$ This would mean that, from $S_n$, if we read $a$, ...
Ben I.'s user avatar
  • 1,710
10 votes
Accepted

Does there exist an equivalent arithmetic circuit for each computable function?

Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions $f:\mathbb{F}^n\rightarrow\...
Ariel's user avatar
  • 13.4k
8 votes

Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?

This is an answer to an attempt at understanding a previous version of the question, and is no longer relevant to the latest question. Your question is: What happens when you use a simulating halt ...
D.W.'s user avatar
  • 161k
7 votes

Why do we need epsilon-transitions in Thompson's construction?

What you're looking at there is what's known as Thompson's construction. The idea is that any node in the regular expression parse tree corresponds to an NFA with a single entry and exit point. To see ...
Pseudonym's user avatar
  • 22.2k
6 votes
Accepted

What is the difference between Simulated Annealing and Monte-Carlo Simulations?

Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness....
Yuval Filmus's user avatar
5 votes

What does "fast-forwarding" mean in the context of CPU simulation?

Here I will complement the perfectly correct information that Paul gave with more gem5 specifics. One major use case for fast-forwarding is when you have to boot Linux/Android and only then run your ...
Ciro Santilli's user avatar
5 votes

Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?

The way i see it, talking about slowdowns on simulations of a specific Turing machine $M_0$ doesn't make much sense. I could always just run $M_0$ and call this a simulation, which will result in no ...
Ariel's user avatar
  • 13.4k
5 votes
Accepted

Brzozowski algebraic method for NFA

Brzozowski's algebraic method is safe as long as you don't have epsilon transitions. It even works if your transitions are labelled by languages not containing the empty word. It may also work if some ...
J.-E. Pin's user avatar
  • 6,159
4 votes

Church-Turing and physical PDEs

The branch of mathematics and computer science that studies these questions is computable mathematics. The general answer is that things tend to be computable. I would add to that the observation that ...
Andrej Bauer's user avatar
  • 30.8k
4 votes

What is a program in self-replicating programs?

The computer's operating system keeps track of which pieces of memory make up which program. The partition into programs is entirely arbitrary, and the only reason a section of memory counts as ...
Tom van der Zanden's user avatar
4 votes
Accepted

Deep DFS traverse on graph

You can compute the exact distribution of $\sum_{i=1}^n s_i$ using dynamic programming: for each vertex $v$, index $m \in \{0,\ldots,n\}$ and index $S \in \{0,\ldots,9m\}$, calculate the number of ...
Yuval Filmus's user avatar
4 votes
Accepted

Quantum computer simulators with proper measurements

Based on QCAD's help file, their measurement gates are more like measure-later-suggestions: The measurement gates on QCAD only set "measurement flags". After the calculation, the measurement is ...
Craig Gidney's user avatar
  • 5,862
4 votes
Accepted

Steps to convert regular expressions directly to regular grammars and vice versa

As (briefly) indicated by Raphael in a comment, the only difference between an NFA and a linear grammar is formatting. You can use any algorithm which converts a regular expression to an NFA, and ...
rici's user avatar
  • 12k
4 votes
Accepted

Is the simulation of how a warehouse functions (eg Amazon) a discrete event simulation problem

Like many real-world models, this type of situation can be modeled both continuously and discretely. For example, if you defined the problem as a series of equations defining the rates at which items ...
Tyler Durden's user avatar
4 votes
Accepted

Proof that PDA's with different definitions have same expressive power

You prove it the same way you prove that any two models of computation are equivalent: you show that, for every machine of type A, the language accepted by that machine is accepted by some ...
David Richerby's user avatar
4 votes
Accepted

Is it 100% OK to say "All software doesn't need to know the system lower than the architecture level"?

Nothing is 100% sure in life. Abstractions are rarely perfect; they can be leaky. Nonetheless, just because developers at higher levels sometimes need to know about lower layers doesn't mean they ...
D.W.'s user avatar
  • 161k
4 votes

Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?

In response to an earlier version: You have misunderstood their proof, which is not very well presented (imho); but you also seem to have cut off the end, where they establish the contradiction. They ...
Raphael's user avatar
  • 72.5k
3 votes
Accepted

Equivalent DPDA that always halts for every DPDA with empty stack language

The look-ahead property for pushdown automata is that a PDA $Z$ can answer certain questions of the form "how would PDA $X$ behave when given my stack", and then make moves based on that information. ...
Hendrik Jan's user avatar
  • 30.8k
3 votes
Accepted

Mealy to Moore Conversion

It is very simple to understand. The Mealy machine has 'm' outputs that means total 'm' transitions possible. Number of states are 'n'. Hence, there are a maximum of m*n transitions possible in ...
Akash Mahapatra's user avatar
3 votes

Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?

No. There is no such proof. There exists a universal Turing machine $U$ and a machine $M_0$ such that $U$ simulating $M_0$ is faster than running $M_0$ directly. For instance, $M_0$ might implement ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Turing Machine with additional finite memory of size $n$

I don't think that you can "embed" the extra memory into the alphabet and "carry" it with the head moving around without a $|Q|$ blow-up (blow-up comparable to the one of approach 1). So a (weird!) ...
Vor's user avatar
  • 12.5k
3 votes

Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

Identify $W$ with the set of all weights. Let $B$ be a basis of $W$ over the rationals. That is, you can write every weight in $w$ as a linear combination of elements of $B$ with rational coefficients....
Yuval Filmus's user avatar
3 votes
Accepted

How to prove a side effect in a function

If the function has two outputs, a standard way to represent this is as a function $f: A \to (B \times C)$, i.e., $f$ outputs a pair of an AST and a symbol table. If the function updates an existing ...
D.W.'s user avatar
  • 161k
3 votes

How to prove a side effect in a function

It depends on how you model the system and what proof approach you're using. For early versions of Hoare Logic, there isn't really any notion of "scope", so there's absolutely nothing special you need ...
Derek Elkins left SE's user avatar
3 votes
Accepted

Solving the Path Explosion Problem in Symbolic Execution

The heuristic approach to solving the path explosion problem picks the next branch to explore based on some function. A simple heuristic function, yet pretty effective, would be to assign the score of ...
Alex Lin's user avatar
  • 106
3 votes
Accepted

Is it reasonable to model row buffers in DRAM corresponding to the same bank ID as one big row buffer?

You can look at how one of the existing DRAM simulators work. Consider, for example, Ramulator, which is a popular academic DRAM simulator. Ramulator Models main memory as a tree of nodes, where the ...
Hadi Brais's user avatar
3 votes
Accepted

Does the callback concept of programming have any basis in computer science?

(I might be wrong, but this is my understanding.) Callbacks, especially as seen in JS, are analogous to a semantic model known as Continuation-passing style (CPS). In CPS, a program’s flow is modeled ...
D. Ben Knoble's user avatar
3 votes

What subfields in computer sciences may one study without learning Object Oriented Programming?

Depending on where you study, you might be able to get a CS degree without Object Oriented Programming, but the chances are slim. Most degrees would require you to take some programming courses using ...
gnasher729's user avatar
  • 30.4k

Only top scored, non community-wiki answers of a minimum length are eligible