Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
0answers
54 views

Real RAMs with “reasonable” operations

There is a large body of literature on RAMs with "reasonable" and "unreasonable" operations, where "unreasonable" operations would yield a machine with too much power to be practically feasible. For ...
0
votes
0answers
60 views

Modified Linear Bounded Automata Language

We know that linear bounded automatons accept context-sensitive grammars. Now suppose that we modify the LBA such that any location of the tape except the input part can be changed.What language ...
1
vote
3answers
215 views

Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?

As the title states. Let's say we have a set of inputs that define a tree structure. Is it possible to construct an automaton that can perform depth-first search on this data that is not Turing-...
12
votes
1answer
303 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 ...
1
vote
1answer
120 views

Who was the first to define the RAM model?

I am working on a project where I refer to the RAM model, I explain what it is, but I am not sure who defined it first. The wikipedia article is not very explicit about it, and the first citation is ...
1
vote
1answer
91 views

Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete?

I have been researching a bit lately and found myself thinking about the title question for some time now, but have found nothing conclusive. For example, some problems require loops practically - ...
4
votes
0answers
100 views

Is a reduced Wang B-machine Turing-complete?

A Wang B-machine has only 4 instructions: right: Move tape head right left: Move tape head left ...
6
votes
1answer
725 views

What is the difference between quantum computing and parallel computing?

Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the ...
5
votes
1answer
976 views

Does every turing machine have an equivalent, single-state, n-tape turing machine?

Is it the case that every problem computable by a Turing Machine can also be represented by some kind of equivalent n-tape Turing Machine which one has only one state? (We can assume that the accept ...
8
votes
1answer
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 ...
7
votes
2answers
1k views

Does there exist an equivalent arithmetic circuit for each computable function?

Does there exist an equivalent arithmetic circuit for each computable function? I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe ...
0
votes
2answers
254 views

Can a 1-tape turing machine simulate a stack?

Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers. I failed to find any ...
36
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 ...
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 ...
4
votes
3answers
614 views

To what extent is my interpretation of computable numbers correct?

Interpretation: Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to ...
3
votes
0answers
114 views

Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
4
votes
1answer
315 views

CLRS RAM model Description

I'm seeking some clarification on a description of the RAM model in CLRS on page 23, section 2.2 (Analyzing Algorithms). Firstly, it is mentioned that we assume integers are represented with $c\cdot\...
4
votes
0answers
61 views

What is the role of abstract machines in the Curry-Howard isomorphism?

By abstract machines I mean things like the SECD machine, Krivine's machine or more generally machines with states/memory/registers/stack/accumulator... According to Wikipedia page of the Curry-...
3
votes
1answer
171 views

Precise definition of oracle classes $A^B$

I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a ...
1
vote
4answers
476 views

Does a computer do only two things?

According to the book, Introduction to Computation And Programming Using Python by John V Guttag, a computer does only two things: Store data Manipulate data But is this all? I mean, without I/O, ...
2
votes
1answer
56 views

How to extent primitive recursion from natural numbers to finite strings?

Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification ...
4
votes
1answer
56 views

Computing with number of stack items

For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete? Is it enough to be able to access just the top-most item? Two ...
3
votes
1answer
599 views

recursive language and computable function

Question: Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable ...
2
votes
2answers
2k views

Meaning of ε in NFA-ε?

In wikipedia NFA-ε transition function defined as follows $Δ : Q × (Σ ∪ \{ε\}) → P(Q)$, where $Σ$ is an alphabet and $ε$ - empty string. I don't understand the meaning of $ε$ in this context. ...
1
vote
1answer
56 views

Is there a known algorithm for computing the n-th Turing machine directly? [duplicate]

Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M_1$ can be represented by 9,900,599 ([0 0 halt],...
0
votes
1answer
105 views

How can a Turing machine write the description of the n-th Turing machine?

I am trying to interpret the following problem: "Describe an algorithm for a Turing machine which receives the integer n as input and proceeds to write the description of the n-th Turing machine from ...
6
votes
1answer
89 views

Does “not regular” imply “acceptor needs memory”?

Regular Languages, by definition, can be accepted by finite automata, which do not have memory. But if I know that a language is not regular, does that imply that any mechanism that recognizes the ...
1
vote
0answers
87 views

Addition Register Machine

In an abstract register machine, is it possible to add two registers together without losing one of the summands, but without using a third register? That is to have a register machine that maps $(m,...
3
votes
1answer
76 views

Do formulas involving fewer repetitions of variables give higher numerical precision?

I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis. Exercise 2.15. Eva Lu Ator, ...
1
vote
3answers
718 views

Why an ARM processor with 32 bits address bus can address 4 billion different bytes?

Why an ARM processor with 32 bits address bus can address 4 billion different bytes? I know that $2^{32}$ is equal to about 4 billions, but shouldn't it be 4 billion bits and not bytes? Hence if I ...
3
votes
1answer
54 views

Prove that $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable

I want to prove that: $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable. Here $w$ is a string and $B(n,w)$ is the set of all $n$-state ...
1
vote
0answers
155 views

Implementation of function [closed]

We have that MIMA (Neumann MInimal MAchine) has the following commands: I want to implement the Mima-command EQL adr (equal?) with the other Mima-commands. We have that for that command it ...
2
votes
4answers
1k views

How does size of a number in an array affect time complexity algorithm analysis?

This question stems from this question and this answer. I also want to preface this question by stating that this question is done from the perspective of a RAM (or PRAM if it's more accurate term) ...
5
votes
0answers
112 views

Is $E_{LBA}$ a Turing-recognizable language? [closed]

I know that $E_{LBA} = \{\langle M \rangle ~ \mid ~ L(M) = \emptyset \}$ is an undecidable language, but is it recognizable (recursively enumerable)? It seems that it's complement is recognizable ...
4
votes
1answer
134 views

Using analog values with Algebraic Normal Form?

Algebraic normal form (ANF) is a way of describing digital circuits made up of AND and XOR gates. The below is an example of an ANF expression which evaluates to true if two or more of it's three ...
2
votes
1answer
72 views

How does universal calculator work?

As I understand, the concept 'computation' started dependent on hardware (like looms for instance). The Hardware defines (physical cascades) what happens between input and output. I think I saw in ...
50
votes
7answers
19k 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. ...
-1
votes
1answer
223 views

In automata theory, why is a machine classified based on the languages it recognises?

Automata Theory is a subject where we mathematically model a computing device and study the theory behind it. Here we group the computing devices based on the number of languages they can accept. ...
1
vote
2answers
295 views

Variant of Turing machine

How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the ...
8
votes
5answers
526 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, ...
0
votes
1answer
32 views

Characterisation of Turing completeness? [duplicate]

I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language. For example, an imperative language is Turing complete if it has ...
1
vote
1answer
127 views

Relation between Machine code and Von Neumann architecture

Since machine language executes instructions on ALU, CPU register and memory, is correct say that machine code abstract the Von Neumann model? If exists, semantically, what is the relation between ...
1
vote
1answer
183 views

Is Functional Complete means Turing Complete?

I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates. A Turing machine may halt or not in a particular ...
1
vote
1answer
138 views

Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine?

It is known that a Turing machine cannot predict the outcome of another Turing machine. Given a machine $M$ less powerful than any Turing machine (i.e. able to decide less languages, i.e. a subset of ...
3
votes
0answers
71 views

Can we define CFL without grammars or automata?

The set of regular languages $R$ over an alphabet $\Sigma$ can be defined as the smallest set satisfying these 5 axioms: Empty language: $\{\} \in R$ Singleton languages: $\forall a \in \Sigma : \{a\}...
3
votes
1answer
842 views

NP with a parallelism model?

Can we think of NP using a parallelism model instead of using a "checking relation" without loss of generality? From what I understand from the problem statement given by Stephen Cook, The ...
2
votes
3answers
589 views

Why does computer have branch and jump instructions

I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist. I am asking what theory ...
1
vote
1answer
287 views

Two-head one way finite memory machine accepts non-regular languages

I'm having trouble proving, or understanding why a two-head one-way finite memory machine could accept a non-regular language– for instance, $(w \mid w \in (a,b)^{*}, w= a^i b^i, i\geq 0)$. For ...
1
vote
1answer
62 views

What problems are solvable in Datalog?

Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what ...
0
votes
2answers
95 views

Can other models of computation equivalent to Turing machines also recognize the same languages?

There are other models of computation equivalent to Turing machines in terms of computability. Turing machines also recognize recursively enumerable languages. My questions are Do other models of ...