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.

64 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19
votes
1answer
298 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 ...
8
votes
1answer
547 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-...
7
votes
0answers
80 views

Automata that is Turing complete if you add a nondeterminism

Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
7
votes
0answers
127 views

Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
7
votes
2answers
298 views

Automaton equivalent of the π calculus?

If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing ...
6
votes
1answer
776 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
0answers
196 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 ...
5
votes
0answers
91 views

Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
4
votes
0answers
37 views

The cost of memory allocation on the (tacitly assumed) Word RAM machine?

Consider a particular algorithm that solves the binary search problem (or similar stuff) by performing $\sqrt{n}$ simple operations on numbers of $\log(n)$ bits. Suppose this algorithm works on a <...
4
votes
0answers
55 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 ...
4
votes
0answers
105 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 ...
4
votes
0answers
62 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-...
4
votes
0answers
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 ...
4
votes
1answer
663 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
4
votes
1answer
139 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 ...
3
votes
0answers
96 views

Alternative to a CALL as a composition?

I've seen a numerous interesting abstract machines (i.e. CESK) and evaluators (diverse meta-circular S-expression evaluators, i.e. vau, COLA) and other models (concatenative, SK/Lambda calculus) which ...
3
votes
0answers
117 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. ...
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
0answers
83 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel ...
2
votes
0answers
109 views

Equivalence between different Turing Machines and a definition of simulation

Im having some difficulty understanding how the following two concepts could be related. Equivalence between TMs as is commonly tought According to this site answer, to prove a standard TM model to ...
2
votes
0answers
37 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
2
votes
0answers
200 views

What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
2
votes
0answers
98 views

Simulating QC using nondeterministic Turing machine

Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine? Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing ...
2
votes
0answers
76 views

Is the set of admissible numberings recursively enumerable?

For each admissible numbering, pick at least one pair of programs (but not necessarily all, which is impossible anyway) where the first translates from a given admissible numbering to that one, and ...
2
votes
0answers
324 views

Explaining TM notation in Lewis/Papadimitriou

I was working on some questions in the book "Elements Of The Theory Of Computation", by Lewis and Papadimitriou, and I need help with one question - question 4.1.8 (chapter 4): Give the full ...
2
votes
0answers
49 views

Typed representation of a memory model

Assume a simple procedural language, where statements write and read from local memory via references and procedures accept arguments of n different scalar types (say floats, ints and strings) and ...
2
votes
0answers
97 views

ORAM: Is it generic?

Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independent of ...
2
votes
0answers
45 views

A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
2
votes
0answers
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 (...
2
votes
0answers
68 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 \}$...
2
votes
0answers
562 views

λ-Calculus extensions: meaning of extension symbols

When working with λ-Calculus I see lots of extensions that use other symbols such as ∀ <:Top {} ←, which are from "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce. ...
1
vote
1answer
13 views

Injectivity verification in o(n) space and O(n) time

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
1
vote
0answers
26 views

Theory for programs that are “embedded” in other programs?

We can make the following distinctions: (I will use the term "program" and "machine" as synonyms). A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes ...
1
vote
0answers
24 views

General notion of memory for a computational model

I have just started studying Michael Sipser's Theory of Computation, studying various computational models such as FAs, PDAs et cetera. In the book, the term "memory" was often used,as in the case of ...
1
vote
0answers
51 views

RO turing machine with finite memory

Consider the following: A weak TM is a TM with finite tape in size $k$ which can only read its input values. note: the tape size does not include the input length. I need to determine whether if the ...
1
vote
0answers
31 views

Alternatives to Sequential Computation

When software boils down to assembly, it is just a sequence of instructions like this: ...
1
vote
0answers
95 views

Doubt on dovetailing

Let < M > be an encoding of a Turing machine. L = { < M > | M is a Turing machine that accepts a string of length 2014 } Above language is R.E(even though we have infinite TM's) as we have ...
1
vote
0answers
56 views

Formal definition of simulation

Assume that the model of computation is a standard Turing machine model with input alphabet $\Sigma = \{0,1\}$, work alphabet $\Gamma = \{0,1,\_\}$, 1 input tape, 1 work tape and 1 output tape. We ...
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,...
1
vote
0answers
102 views

Generate a graph to exact size using Kronecker product graph model

In network science, we can take sample a complex system and derive from this sampling a representative network (or graph) that describes the system to some extent. A model of a network, is a powerful ...
1
vote
0answers
124 views

Construct DFA given oracle access to the language

I was given the following question. Given a minimal DFA $A$ with $m$ states over some alphabet $\Sigma$ which is a "black box" (you can only run words to it and it tells you if it accepts or not): ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
284 views

Reducing states in a finite-state machine using compatibility classes, for an incompletely specified machine

In the process of reducing the states of a synchronous finite state machine first we need to create maximal compatibility classes (of states; which states can be compatible, i.e. the "don't cares" can ...
0
votes
0answers
25 views

why does the pumping lemma want us to only consider the first repitition of states?

In Sipser's Intro to Theory and computation, He writes: I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
0
votes
0answers
11 views

State-machine semantics of instruction set architectures

An instruction set architecture is an abstraction, a common interface layer between the software and the micro-architecture. The existence of this clearly delineated interface is becoming increasingly ...
0
votes
0answers
20 views

Can we use Wifi signals readings to estimate 3D shapes?

I don't know if this is the appropriate SE for this question, but I hope someone would answer !
0
votes
0answers
28 views

Is the proof for the undecidability of $A_{TM}$ still valid if we change certain parts?

i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book). on page ...
0
votes
0answers
79 views

RAM and Turing machines: time complexity of simulation

My RAM machine is very simple: it has $k$ tapes, an input tape and one special control tape it has an infinite memory (array called $A$) which can be accessed randomly the control tape is read ...
0
votes
0answers
33 views

What is “Phrase structure grammar”?

I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar: Type-0 grammars generate recursively enumerable languages. The ...