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

371 questions
Filter by
Sorted by
Tagged with
7k 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?...
14k 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 ...
20k 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. ...
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 ...
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 ...
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 ...
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 ...
9k 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 ...
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 ...
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 ...
32k 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 ...
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: ...
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: ...
3k 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 ...
290 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 ...
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 ...
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 ...
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/...
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 ...
502 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 ...
910 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, ...
918 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 ...
663 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,...
887 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 ...
7k 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?
313 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 ...
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 ...
232 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 ...
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 ...
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 @...
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 ...
394 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 ...
405 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, ...
516 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 ...
2k 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 ...
674 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 ...
482 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", ...
1k 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 ...
367 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 ...
1k 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 ...
632 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 ...
3k 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 ...
527 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, ...
413 views

### How do nondeterministic Turing machines compute general function problems?

(Hope this hasn't been asked before, but I didn't find anything.) In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. ...
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 ...
227 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 ...
220 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 ...
252 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 <...
520 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 computational-...
3k views

### Why do pushdown automata use a stack?

I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?