Questions tagged [computation-models]

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.

Filter by
Sorted by
Tagged with
76
votes
2answers
8k views

What does the “Lambda” in “Lambda calculus” stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the term?...
70
votes
6answers
15k views

Why is the Turing Machine a popular model of computation?

I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we ...
56
votes
7answers
21k views

Is a Turing Machine “by definition” the most powerful machine?

I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that. ...
52
votes
2answers
6k 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 ...
45
votes
7answers
11k views

Is there anything that MUST be done on a multi-core CPU?

When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing ...
38
votes
3answers
4k views

How is algorithm complexity modeled for functional languages?

Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case ...
36
votes
2answers
2k 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 ...
32
votes
7answers
10k views

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
30
votes
5answers
38k views

Difference between a turing machine and a finite state machine?

I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one ...
29
votes
4answers
4k views

What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?

I encountered below statement by Alan M. Turing here: "The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are ...
27
votes
7answers
5k views

Is there a physical analogy to the Turing Machine?

Recently in my CS class I've been introduced to the Turing Machine. After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine. I was ...
23
votes
8answers
7k views

Programming language where every expression makes sense

Per recommendation I am reposting this from Stack Overflow. Recently I have been thinking about following issue. Consider the code for a standard "Hello world!" program: ...
23
votes
3answers
4k 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 ...
22
votes
1answer
380 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
21
votes
5answers
4k views

Could the Halting Problem be “resolved” by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...
18
votes
5answers
6k views

Why is a quantum computer not capable of solving more problems than a classical computer? [duplicate]

On the Wikipedia page for quantum algorithm I read that [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable ...
18
votes
4answers
2k 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 ...
18
votes
3answers
570 views

What specifically makes quantum computers useful?

I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic. That seems to be what people point to as being what makes quantum ...
17
votes
8answers
7k views

Why can we assume an algorithm can be represented as a bit string?

I am starting read a book about Computational Complexity and Turing Machines. Here is quote: An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical ...
17
votes
5answers
1k 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 (input/...
16
votes
1answer
756 views

Quantum Computing - Relationship between Hamiltonian and Unitary model

When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, Goldstone,...
16
votes
1answer
1k views

Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, ...
16
votes
1answer
1k views

Universal simulation of Turing machines

Let $f$ be a fixed time-constructable function. The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given the description of ...
14
votes
2answers
982 views

Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
13
votes
9answers
9k views

Why does a Turing machine recognise exactly one language?

I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?
13
votes
3answers
258 views

Is there an abstract machine that can capture power consumption?

When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to ...
13
votes
1answer
393 views

Random Access Machines with only addition, multiplication, equality

The literature is fairly clear that unit-cost RAMs with primitive multiplication are unreasonable, in that they cannot be simulated by Turing machines in polynomial time can solve PSPACE-complete ...
12
votes
3answers
2k views

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions? Edit: I am new to ...
11
votes
2answers
2k views

Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines. However, Linearly Bounded Turing Machines are also ...
11
votes
3answers
521 views

Why nondeterminism?

Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
11
votes
4answers
614 views

Why is the tape not part of the definition of a Turing Machine?

I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, ...
11
votes
3answers
437 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 ...
10
votes
3answers
2k views

Infinite calculations in finite time

This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to ...
10
votes
1answer
4k views

What is the difference between RAM and TM?

In algorithm analysis, we assume a generic one processor Random Access Machine (RAM). As far as I know, the RAM machine is no more efficient than the Turing machine. All algorithms can be implemented ...
10
votes
1answer
1k views

Algorithm Complexity Analysis on functional programming language implementations

I've learned today that algorithm analysis differs based on computational model. It is something I've never thought about or heard of. An example given to me, that illustrated it further, by User @...
10
votes
1answer
646 views

Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)

The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach: Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this ...
9
votes
6answers
3k views

Do Turing machines assume something infinite at some point?

In a previous question What exactly is an algorithm?, I asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm. One of the ...
9
votes
2answers
795 views

Analog computers and the Church-Turing thesis

I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine): One class of challenges to the strong Church–Turing ...
9
votes
2answers
520 views

Is there a clear definition of “computable” for models of computation which are not turing complete?

This is a follow-up of another question here, and I hope it is not too philosophical. As Raphael pointed out in a comment on my previous question, I don't really get the definition of "computable", ...
9
votes
1answer
2k views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
9
votes
2answers
502 views

Is integer sorting possible in O(n) in the transdichotomous model?

To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem: Given a sequence of length $n$ consisting of finite integers, find the permutation where every ...
9
votes
1answer
293 views

Expressiveness of modern regular expressions

I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like <...
8
votes
2answers
646 views

Can a quantum computer (theoretically) do things a classical computer (literally) can't? [duplicate]

I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer ...
8
votes
5answers
549 views

Why are progress bars so inaccurate? [closed]

Computers and programming languages tend to be deterministic and predictable. Yet progress bars seem the opposite, especially if the operation is complex. Even for world class professional products, ...
8
votes
3answers
2k views

Differences between programming model and programming paradigm?

What is the relation and difference between a programming model and a programming paradigm? (especially when talking about the programming model and the programming paradigm for a programming language....
8
votes
1answer
1k views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation. I was wondering whether combinational ...
8
votes
2answers
448 views

Mathematical model on which current computers are built

It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists ...
8
votes
2answers
239 views

Which theoretical parallel model is closest to CUDA?

Which theoretical parallel model is closest to CUDA/OpenCL programming model? For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too ...
8
votes
1answer
143 views

Are weakly polynomial time algorithms truly polynomial?

I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia states an algorithm runs in strongly polynomial time if ...
8
votes
1answer
242 views

I built a mechanical computer powered by marbles. What are its theoretical limitations?

Over the last couple years, I built a mechanical computer powered by marbles and made a game out of it. It's similar to the old Digi-Comp II, except for two key differences: Parts are repositionable ...

1
2 3 4 5
9