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

400 questions
Filter by
Sorted by
Tagged with
106 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 ...
303 views

### Is there any data structure that can't be represented or described inside a computer?

We all know that, at least theoretically, there are several possible models of computation, varying in structure. Strictly speaking, there are several (not just one) models of computation that exist ...
458 views

### How Turing recognizer accepts any string?

I've got a basic doubt for such I'm not getting convicting argument. See, We say a TM $M$ is Turing recognizer if it accepts a string belonging to the language $L(M)$ & says $yes$ if the string ...
114 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 ...
18 views

### what interpolation method can I use for reliefs

I need to know which interpolation method is the best for working with reliefs, that is, to know the elevations or depths of a given terrain a set of points.
75 views

### Why models of computation are primarily focused on machines?

It seems a lot of courses (like this and this) on theory/models of computation (and even formal languages) cover DFA, NDFA, PDA, and TM in the order of increasing computational power. This of course ...
433 views

### Comparing non-deterministic and also the deterministic expressive power of FA, PDA's and TM'S [closed]

I am sorta confused and also could not find a answer online, but in terms of expressive power, . Non-deterministic FA, PDA, TM NFA < NPDA < NTM ...
229 views

### Proving infinity of CFL with pumping lemma

Given a CFG G in Chomsky Normal Form with n variables. Prove that $|L(G)| = \infty \iff \exists w \in L(G)$ such that $2^n<|w|\le2^{n+1}$ Now, proving left to right I've encountered a problem. ...
86 views

### Closure of a CFL under specific operation

Consider the following operation on language $L$: $\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$ I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
32 views

### How does it demonstrate that the computational model of rewriting is adequate?

How can I demonstrate that the computational model of rewriting is adequate? For example, with it, it is possible to compute any computable function.
63 views

### Register model of computation

It consists of one read only input memory and write only output medium. The computation proper takes place in a working memory of limited size. When stating that a problem can be solved with a certain ...
199 views

### Is there a limit on transition function compositions in NFAs?

I want to prove regularity of a language that contains a known regular language $L$ using an NFA. Say the transition function of the automation that accepts $L$ is $f$. In my new transition function,...
389 views

### How powerful are DFA with recursive calls?

A family of deterministic finite automata of degree $n$ over an alphabet $Σ$, with $\bigcap Σ = ∅$, consists of a set $\mathcal{A} =\{(K_i,Σ∪\{1,\dots,n\},δ_i,s_i,F_i) : 1 ≤ i ≤ n\}$ of ...
49 views

### Reducibility and Artificial Neural Networks

I have read (here and here ) about the computational power of neural networks and a doubt came up. There is a way to reduce an ANN to another ANN (not taking into count the training algorithm) ? e.g. ...
291 views

### Given a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$?

1) (cited from "Introduction to the Theory of Computation" by Michael Sipser) Let $M$ be a Turing machine, we say that $M$ decides a language $L$ if $M$ is a decider which recognizes $L$. 2) (...
730 views

### Are finite state transducers and Mealy machines the same machines?

There are several versions of the definitions of the FST and the Mealy machine. Some of the definitions are almost same. Some have a little differences. But it seems that they both are a kind of DFA ...
848 views

### Working of NPDA

I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example ...
84 views

### Given a sufficiently powerful computer and model, can dice rolls be predicted?

I guess that this is a chaos, randomness and modelling question. Can it be conceived that a sufficiently powerful (perhaps quantum) computer might be able to accurately predict the scores on a ...
332 views

### Set theory and computer science

It's said that in Zermelo–Fraenkel set theory (ZFC) one can develop all of mathematics. How about computer science? Is it possible to define algorithms as a first step? More specifically, how to ...
290 views

### Is effective solvability a coherent and/or useful concept? [closed]

I am aware of Turing's proof of the undecidability of the halting problem (and I think I understand it). What I'm asking is quite different. I shall define what I mean by "effectively solvable": ...
267 views

### Infinite Boolean circuits as a model of computation

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
1k views

### Is there a formalization of the computational model for quantum computers?

There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, ...
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 ...