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 (1)

1
vote
1answer
61 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. ...
4
votes
0answers
51 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 ...
1
vote
2answers
146 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 ...
0
votes
0answers
35 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 ...
5
votes
0answers
90 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 ...
1
vote
1answer
39 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 ...
0
votes
3answers
85 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 ...
5
votes
3answers
70 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 ...
2
votes
0answers
38 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 ...
2
votes
0answers
40 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 ...
2
votes
1answer
49 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 ...
1
vote
1answer
150 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 ...
18
votes
9answers
6k 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: ...
3
votes
1answer
35 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. ...
1
vote
1answer
45 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 ...
1
vote
1answer
189 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 ...
2
votes
7answers
88 views

Is infinitely fast computer fundamentally impossible even theoretically?

This may get slightly philosophical, but consider the following program: ...
7
votes
1answer
262 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 ...
4
votes
1answer
53 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 ...
11
votes
3answers
241 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 ...
3
votes
2answers
58 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 ...
3
votes
3answers
69 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. ...
4
votes
0answers
18 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 ...
2
votes
0answers
16 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 ...
5
votes
2answers
129 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 ...
2
votes
1answer
109 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 ...
0
votes
0answers
13 views

Total Turing Machine Grammar [duplicate]

We know that the Turing Machine corresponds to the 'Unrestricted' set of grammars. To what set of grammars does the Total Turing Machine correspond?
0
votes
1answer
46 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 ...
9
votes
3answers
1k 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 ...
6
votes
2answers
120 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 ...
7
votes
3answers
203 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, ...
2
votes
1answer
49 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 ...
13
votes
5answers
4k views

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

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 ...
12
votes
5answers
3k 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: ...
0
votes
1answer
72 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 ...
5
votes
1answer
124 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?
3
votes
2answers
93 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 ...
2
votes
1answer
39 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 ...
4
votes
2answers
123 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 ...
0
votes
0answers
19 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 ...
1
vote
0answers
31 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 ...
5
votes
3answers
103 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 ...
9
votes
1answer
259 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, ...
7
votes
1answer
78 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 ...
2
votes
3answers
115 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 ...
12
votes
0answers
97 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 ...
1
vote
2answers
41 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 ...
1
vote
1answer
74 views

Computer Programs and lambda terms without normal form

λ-calculus an ideal mathematical model in which to interpret programs. A program can be interpreted as a lambda term, and the term can have or not have a normal form. What role the terms without ...
2
votes
0answers
37 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R ...
1
vote
1answer
77 views

RAM Machine and FSM

I heard it's possible to model a bounded-memory RAM as a Finite State Machine. I'm curious about the method of how we would that. Does anyone have a clue ? Thanks in advance