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.

learn more… | top users | synonyms

4
votes
2answers
325 views

Convex Hull algorithm - why it can't be computed using only comparisons

Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that: ...
-1
votes
2answers
69 views

Tricky Turing Machine state diagram

what would the Turing machine state diagram be for this language: $A=\{ (0 \cup 1)^a(1 \cup 2)^b(2\cup 3)^c \mid a \geq b\} $ ? how would the turing machine design know the size of $(1 \cup 2)^b$ ? ...
-1
votes
1answer
58 views

Proving a language is context free by coming up with a context free grammar for the language [closed]

Let A and B be languages over $\sum$ = {0, 1, 2, 3} Language A = {$(0U1)^a(1U2)^b(2U3)^c | a \geq b$} Language B = {$(0U1)^a(1U2)^b(2U3)^c | a = c$} Question: prove that A and B are context free
3
votes
3answers
138 views

why is this computational method by Knuth “effective” and “powerful”?

This is a follow-up question regarding Knuth's one formulation of the concept of an algorithm here. I am asking it here because I do not have enough reputation to post a comment to that question. To ...
3
votes
1answer
75 views

How to convert a Turing Machine program to a tiling using Wang Tiles?

This is a cross-post from a post on MathSE due to lack of answers. To illustrate my question I provide the following example. The website Online Turing Machine provides a Turing Machine simulator. ...
0
votes
0answers
29 views

Recursive set - How to show a language is undecidable [duplicate]

I am currently working on the following task: A language L = {< M> | M(x) = x^2} is given. Now I need to show, that this language is not decidable. By the way, < M> is the Gödel number But ...
1
vote
1answer
76 views

Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings [closed]

The following is a homework assignment. I am looking for criticism / feedback on my solution, and I have a specific question. Suppose $L$ is a language over $\Sigma$, and $x_1, x_2, ... , x_n$ are ...
4
votes
1answer
194 views

How to prove the structured program theorem?

Wikipedia: The structured program theorem [...] states that [...] any algorithm can be expressed using only three control structures. They are Executing one subprogram, and then another ...
1
vote
1answer
27 views

Can a loop be expressed by only the sequence of statements and the choice of statements?

The theorem of structured programming says that any algorithm can be expressed by those three control structures: Sequence Selection Iteration Isn't it possible to rewrite any loop using a finite ...
5
votes
1answer
50 views

Tag system variant

Is there an "official" name for this slight variant of the well known Tag System model of computation, and/or has it been used somewhere? a finite alphabet of symbols $\Sigma$ a halt symbol $H$ an ...
5
votes
0answers
67 views

Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
1
vote
1answer
69 views

In the “tall cache assumption” what does $\Omega$ represent?

Within the field of cache-oblivious algorithms the ideal cache model is used for determining the cache complexity of an algorithm. One of the assumptions of the ideal cache model is that it models a ...
0
votes
0answers
87 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} ...
5
votes
2answers
115 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
511 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
241 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
122 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
454 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 ...
3
votes
2answers
131 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
386 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 ...
8
votes
1answer
232 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
516 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 ...
5
votes
3answers
531 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
185 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 ...
8
votes
3answers
317 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 ...
19
votes
1answer
427 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
299 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 ...
11
votes
4answers
573 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 ...
30
votes
2answers
2k 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 ...