16
votes
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 ...
- 81.4k
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.♦
- 156k
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$, ...
- 1,682
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\...
- 13.3k
9
votes
Accepted
Why is simulation by non deterministic Turing machine faster than a deterministic one?
First of all, simulation of non-deterministic universal TM is better than simulation of deterministic universal TM only time-wise. But number of parallel executing threads is very high. In parallel ...
- 4,807
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.♦
- 156k
7
votes
Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?
Part of the issue with the idea of "proving" the Church-Turing thesis is that the Church-Turing thesis isn't a precise mathematical statement. Rather, it's the idea, or "belief" if you will, that any ...
- 9,037
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 ...
- 21.7k
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....
- 275k
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 ...
- 6,014
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 ...
- 151
4
votes
Accepted
How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?
First of all, you don't simulate an infinite board. You simulate larger and larger boards, until the percolation threshold seems to stabilize. For a given size of board, you need to decide on what ...
- 275k
4
votes
Accepted
Polynomial hierarchy: inclusion between spaces
Using the definition of Papadimitrou for polynomial hierarchy, or for that matter from wiki, the proof is really simple. $\Delta^P_{k+1} = P^{\Pi_k^P} \subseteq CoNP^{\Pi_k^P} = CoNP^{\Sigma_k^P} = \...
- 4,807
4
votes
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 ...
- 275k
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 ...
- 13.2k
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 ...
- 275k
4
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 ...
- 13.3k
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 ...
- 5,802
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 ...
- 30k
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 ...
- 81.4k
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 ...
- 678
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 ...
- 11.9k
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.♦
- 156k
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 ...
- 72k
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!) ...
- 12.4k
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....
- 275k
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.♦
- 156k
3
votes
Accepted
Why is universal turing machine considered with only one head?
There are two (related) answers to your question. The first answer is that the time complexity classes are traditionally defined using one-head Turing machines. For the diagonalization argument to ...
- 275k
3
votes
Every non deterministic Turing machine has an equivalent deterministic Turing machine Formal proof
There is a full proof in Hopcroft, Motwani and Ullman's Book (John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation). There is ...
- 4,807
Only top scored, non community-wiki answers of a minimum length are eligible