The definition of the set of allowable operations used for computation and their respective costs. Some examples of models include Turing machines, recursive functions, lambda calculus, and production systems.
0
votes
0answers
36 views
The complement of the acceptance problem reduces to the acceptance problem: ${A_{TM}}{ \le _M}\overline {{A_{TM}}} $ is this claim true?
If ${A}{ \le _M} {{B}} $ then $\overline A { \le _M}\overline B$ since the mapping reduction function is computable.
So, if ${A_{TM}}{ \le _M}\overline {{A_{TM}}} $ then $\overline{A_{TM}}{ \le _M} ...
4
votes
2answers
80 views
Is there an always-halting, limited model of computation accepting $R$ but not $RE$?
So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages.
I'm wondering, is ...
5
votes
4answers
185 views
What is the exact relation between programming languages and Turing machines?
I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, ...
1
vote
0answers
127 views
λ-Calculus extensions: meaning of extension symbols
When working with λ-Calculus I see lots of extensions that use other symbols such as
∀ <:Top {} ←, which are from "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce.
...
0
votes
3answers
106 views
Looking for some more details on “Turing” devices
I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I ...
4
votes
2answers
259 views
Models of computation: the arithmetic model, Turing machine (and …)
How is an arithmetic model defined?
What relations are between it and Turing machine? Are they equivalent in some sense?
Is it true that
in the arithmetic model of computation, the basic ...
2
votes
2answers
102 views
Quantum computing 'amplitudes'
As far as I understand, you receive an output from a quantum computer for an algorithm in the form of an amplitude, which is one of the many states your qubits may be in, however this amplitude is a ...
8
votes
3answers
197 views
How to show two models of computation are equivalent?
I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea ...
7
votes
1answer
164 views
Turing Machine-Like Formalism for The Actor Model
Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.
The Actor Model is sometimes mentioned as a more powerful ...
6
votes
3answers
471 views
Is a PDA as powerful as a CPU?
This is a question I have stumbled upon in my exam revision and I find it intriguing:
My computer is blue and it has a massive graphics card and a DVD and every-
thing so which is more powerful: my ...
4
votes
3answers
347 views
Please explain this formal definition of computation
I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts::
Let $A$ be a ...
6
votes
1answer
124 views
What is a good reference to learn about state transition systems?
I am studying different approaches for the definition of computation with continuous dynamical systems. I have been trying to find a nice introduction to the theory of "State transition systems" but ...
7
votes
3answers
224 views
What is required for universal analogue computation?
What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient?
Also, does anyone know exactly what ...
17
votes
1answer
326 views
Quantum lambda calculus
Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to ...
8
votes
3answers
289 views
Notions of efficient computation
A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing ...
9
votes
4answers
473 views
Is interaction more powerful than algorithms?
I've heard the motto interaction is more powerful than algorithms from Peter Wegner. The basis of the idea is that a (classical) Turing Machine cannot handle interaction, that is, communication ...
26
votes
2answers
953 views
How to define quantum Turing machines?
In quantum computation, what is the equivalent model of a Turing machine?
It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing ...
