# Tag Info

Accepted

### Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

How would you prove that the machine is faithfully simulating a brain? How would you prove that it doesn't matter if you simulate my brain or your brain or somebody else's brain? Church–Turing ...

### 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 ...
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$, ...
Accepted

### Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

No, that wouldn't prove the thesis. Human beings are allowed to use machines. For example, an important consequence of the Church-Turing thesis is that computers can only compute Turing-computable ...

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

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

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

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

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

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