The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

Filter by
Sorted by
Tagged with
0
votes
1answer
183 views

What is the definition of computable partial function?

Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input ...
1
vote
1answer
68 views

Proving the equivalence of two definitions of NFA acceptance

Recall that an NFA $N = (Q,\Sigma,\delta,S,F)$ accepts $w=w_1w_2\ldots w_n$, where $w_i \in \Sigma$, if one of the following holds: (a) $\hat\delta(S,w) \cap F \neq \emptyset$, where $\hat\delta\...
7
votes
3answers
4k views

Why do pushdown automata use a stack?

I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?
1
vote
1answer
52 views

Is there a model of computation based on discrete event dynamic systems?

I asked a question here about discrete event dynamic systems. They are systems whose state evolution depends on asynchronous events. It can be combined with flow to produce a hybrid system. There ...
0
votes
1answer
71 views

Definition of “overhead”

I am writing a paper on the invariance thesis introduced by Cees F. Slot and Peter van Emde Boas as; 'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and ...
1
vote
1answer
73 views

Point and Application of Recursive and Recursive Enumerable Languages

What is the point and application of recursive and recursive enumerable languages. Finite Automaton is used for pattern matching, designing computer architecture and protocols, CFG is used for ...
1
vote
2answers
64 views

Are all computational complexity results oracle results?

When talking about the complexity of a given operation, say multiplication of numbers, one usually counts the number of "elementary operations" that are required. For example, a common argument says ...
4
votes
0answers
42 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 <...
1
vote
0answers
31 views

Alternatives to Sequential Computation

When software boils down to assembly, it is just a sequence of instructions like this: ...
2
votes
1answer
39 views

Potential General Model of Computation with Physics?

I posted a question about a month back regarding the significance of Turing machines (relative to other models of computation). In that post, I mentioned vaguely some conversion between an input ...
0
votes
1answer
108 views

What are the general applications of Computer Science in the field of Psychology?

I am keenly interested to do a project in Computer Science that can aid to address the problems in the field of Psychology. Now I want to know what are the most general and research-oriented issues or ...
-1
votes
1answer
600 views

PCP is decidable over the unary alphabet

Show that the Post Correspondence Problem (PCP) is decidable over the unary alphabet ? = {0}.
1
vote
1answer
75 views

An axiomatic theory of computational models?

There are many different computational models, e.g. Turing machines, register machines, lambda calculus, etc. I am wondering if there exists an axiomatization of computation, that abstracts away ...
-1
votes
2answers
42 views

do the ram lose what it remembers when the power if cut off?

after shutting down the computer do the ram loses what it remember ? if yes is there some technics that are used to get what is stocked into the ram after shutting down the computer ?
4
votes
1answer
743 views

Do “Type-2” Turing machines with infinite length inputs have more computational power?

Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of ...
0
votes
0answers
54 views

Variable bytes (bit arrays) and flipping single bits?

My interest is strictly theoretical at this point, but ultimately applied. Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ...
67
votes
6answers
14k views

Why is the Turing Machine a popular model of computation?

I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we ...
3
votes
1answer
112 views

What's the difference between transdichotomous model and RAM?

In Wikipedia, it says the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size. However, a random access machine ...
3
votes
1answer
607 views

Real life applications of finite automata

I have some confusion about the differences between finite & infinite. can someone tell me how the Toll machine or Park meter, soda vending machine can be used with infinite language? if not, ...
2
votes
1answer
109 views

What is the computation model of Prolog?

Several computation models have representative programming language counterparts, as, according to this answer, Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus, and ...
17
votes
8answers
7k views

Why can we assume an algorithm can be represented as a bit string?

I am starting read a book about Computational Complexity and Turing Machines. Here is quote: An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical ...
3
votes
1answer
200 views

Understanding Applicative Evaluation Order with the Z-Combinator

I am trying to understand how the Z-combinator (Y-combinator for applicative order languages) definition came about. As Python is applicative I am using Python for this. So I know Python's evaluation ...
7
votes
2answers
871 views

$\lambda$-calculus, is there encoding of for or while?

In $\lambda$-calculus, we can encode arithmetic, numbers, booleans, and even compute factorials of numbers, as shown here. Is there encoding of "for" or "while"?
2
votes
2answers
308 views

Solve every problem with recursion [duplicate]

Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks
5
votes
3answers
236 views

Defining computable functions on arbitrary sets

Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to ...
0
votes
0answers
56 views

Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...
1
vote
0answers
64 views

Proof that the language is not regular (Pumping Lemma) [closed]

I have to prove that the following language is not regular: $$\{ x | x = 10^{2n} + 10^n + 1, n ≥ 1\}$$ I am trying to prove it using Pumping Lemma, however, when I expand the expression I have both ...
7
votes
1answer
276 views

Why nondeterminism?

Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
1
vote
2answers
83 views

Time complexity of expanding decimal to new base

There is already a post on this topic on stackoverflow. Nevertheless, I am asking the question here again, primarily because I do not understand the answer given there, and also because I have some ...
2
votes
1answer
250 views

How $N$ qubits correspond to $2^N$ bits?

I read everywhere that $N$ qubits correspond to $2^N$ bits. Let's start with 1 qubit, which is commonly represented by $\alpha |0\rangle + \beta |1\rangle$ where alpha and beta are complex numbers. ...
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 ...
4
votes
2answers
282 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 ...
-1
votes
2answers
325 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 ...
1
vote
0answers
96 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 ...
0
votes
0answers
17 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.
2
votes
1answer
72 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 ...
1
vote
0answers
305 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 ...
0
votes
0answers
155 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. ...
0
votes
1answer
73 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 ...
0
votes
0answers
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.
1
vote
1answer
62 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 ...
1
vote
2answers
192 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,...
2
votes
1answer
327 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 ...
1
vote
1answer
46 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. ...
1
vote
1answer
238 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) (...
3
votes
1answer
557 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 ...
3
votes
1answer
652 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 ...
1
vote
3answers
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 ...
4
votes
1answer
277 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 ...
0
votes
4answers
260 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": ...