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

### About the SOS degree of a function and optimization algorithms for the function

Given a non-negative function on the hypercube $f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$ one says that it is of "SOS-degree" of $d$ (denoted as $deg_{SOS}(f) =d$) if $d$ is the minimum $k$ such ...
274 views

### Turing machine that can tell if it ends in standard position?

Suppose we have a TM $M$ with alphabet $\{0, 1 \}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape ...
247 views

### Why is universal turing machine considered with only one head?

While defining the following time hierarchy theorem (for deterministic case ) : If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$ The ...
324 views

### Explanation for indirect addressing

While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump. ...
138 views

### Advances in recent time in Von-neumann self replication idea

I have read about Von-neumann self replication from Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing ...
902 views

### Turing machine - infinite tape - does that thing exist?

Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist? Do we have the right to regard a machine (a construct) in the same ...
66 views

### What can be said about the Halting Problem if we can include the halting status to the input?

I was reading about Turing Machines and the Halting Problem, i understand that you need an oracle to decide whether given input will halt or loop forever. But why do we need an oracle if we can ...
195 views

### Computational power of Actor Model

In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine. In his paper "Actor Model of Computation: Scalable Robust Information ...
60 views

### Can computation models be categorized in terms of efficiency?

It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other ...
2k views

### Can a Turing Machine have infinite accept states?

I'm still fairly new to Turing Machines, but I've been doing some research. I know that a Turing Machine can have an infinite tape and that it requires a finite number of states, but does it ...
125 views

### What does it mean to be “independent of machine model”?

I have often heard people mention off-hand that the class $\mathsf{P}$ is "machine-independent", or "independent of machine model", or "invariant under change of machine model" - something to do with ...
64 views

### Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (...
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....
411 views

### A model of computation vs an abstract machine

Wikipedia says A model of computation is a formal description of a particular type of computational process. The description often takes the form of an abstract machine that is meant to perform ...
3k views

### Can a Turing machine have infinite states?

Does it make sense for a Turing machine to have infinite number of states ? I had previously asked a question Can Turing machines have infinite length input. From which I came to know about Type-2 ...
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: ...
60 views

### Is modulus capable of universal computation?

I heard once that you could translate any digital circuit into a modulus operation, perhaps modulusing against different numbers? It was a long while ago though and don't remember where I heard it. ...
119 views

### Are Cellular Automata always computers?

I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer. In the introduction part: Cellular automata can be viewed ...
531 views

### In principle, what is the relation between Artifical Intelligence and Turing machine?

I am working on my cs project about AI & Turing machines, so i know that Artifical Intelligence is meant to implement different algorithms into the machine {the computer} to solve a problem or a ...
226 views

### Is infinitely fast computer fundamentally impossible even theoretically?

This may get slightly philosophical, but consider the following program: ...
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 ...
247 views

### Generative power and classification of matrix grammars

[Edited] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy. In here it is stated that: A matrix grammar ...
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 ...
92 views

### How Cellular Automata is related to Automata Theory?

I have read about Automata Theory where it is about the study of abstract machines and automata. And i know that an abstract machine takes the input, process it and create the output, just like ...
2k views

### Computational problem - definition

How should I understand the definition of computational problem? A computational problem is a mathematical object representing a collection of questions that computers might be able to solve. For ...
34 views

### Computational complexity of emulating (untyped) λ-calculus with a queue machine

I am looking for bounds - both lower and upper - on the time, spacial, and state/symbol (i.e. number of states and symbols required) complexity of simulating the (untyped) λ-calculus with a queue ...
22 views

### Complexity bounds for Turing equivalence [closed]

I am looking for bounds - both lower and upper - on the time and spacial complexity of simulating Turing-complete systems with each other. (I am aware that both time and space are ill-defined with ...
272 views

### How to prove universality in complex systems?

I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once. The ...
316 views

### Does solving mathematical equations with Cellular Automata structures means it is universal?

I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure. The ...
98 views

### Quantum computer memory size

Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers). Does it also hold for memory size? Are QC going to have ...
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 ...
301 views

### Are Elementary Cellular Automata structures considered to be fractals?

I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata. But, what about the other rules from ...
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, ...
121 views

### Chomsky hierarchy type determined by language

I have some modified automata and the task is to give the type of Chomsky hierarchy to it. All task is between type 3 and 0 noninclusive. For regular languages there are lot of tools and I can check ...
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 ...
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: ...
87 views

### Model paths by regular languages [closed]

I want use DFA to describe a sequence of movements in a 2D-space (language will be the path accepted by automaton in a particular case). That is a typical modeling problem: how can I encode a ...
384 views

### Simplest Turing-complete ruleset for Markov algorithm

Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?
118 views

### Classical Computation without NOT

Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible ...
130 views

### Disprove that a function exists that counts the turing machines that halt on $\epsilon$

Let $L(M_k) = \{ \langle M \rangle | M \text{ halts on }\epsilon \} \cap \Sigma^k$ Disprove that $\exists f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$. I am not sure where I am ...
416 views

### Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
25 views

### Is there a good model of computation for real numbers? [duplicate]

/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms. The integer numbers case Many algorithms use integers and their ...
38 views

### Markov algorithm: pick rule first, then position, or the other way around?

A Markov algorithm is a string rewriting system (well, not a set of rules but a list of rules since they need to be ordered) with a strategy for applying rules that ensures determinism. I think the ...
326 views

### Are deterministic and nondeterministic Cellular Automata equivalent?

It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs. I ...
912 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, ...
161 views

### Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
185 views

### Is there a name for an inverted state machine?

I recently needed something like a state machine, but with a slightly different use case. In general, I would say a state machine knows about a set of states, and different events. Depending on the ...
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 ...
48 views

### Transitions triggered by sets of events

In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a ...