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.

-1
votes
2answers
41 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
684 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
48 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 ...
2
votes
1answer
86 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
526 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
95 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
187 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 ...
6
votes
2answers
695 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
291 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
206 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
52 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
59 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 ...
5
votes
1answer
200 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
61 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
203 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
91 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
270 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
282 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
93 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
71 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
275 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
136 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
65 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
61 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
186 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
298 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
215 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
467 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
597 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
83 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
244 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
252 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": ...
2
votes
1answer
188 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 ...
5
votes
3answers
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, ...
1
vote
0answers
55 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 ...
2
votes
1answer
97 views

Theory of Turing machine which outputs Turing machine?

I understand the notion of the universal Turing machine ($U$), which receives a pair of Turing machine ($M$) and an input to $M$ ($x$). If $M$, which obtains $x$, outputs $y$, $U$, which obtains $(M, ...
1
vote
1answer
43 views

Verifying execution of code in trustless environment

Let us assume I have a Program P running on remote computer generating output O. Without trusting the remote environment and not having to verify the output O, is there is a way to validate that ...
1
vote
1answer
131 views

How are Qubits useful?

I'm aware that a qubit can exist in an infinite number of states and that when measured it collapses into one state, with the probability of each state being directly affected by it's latitude. My ...
0
votes
2answers
2k views

How can blank be written on the tape if it is not part of input alphabet?

I have read that input alphabet of Turing machine is subset of tape symbols because in input alphabet we don't allow blank symbol. But when ever there is a transition to final state the transition as (...
0
votes
1answer
73 views

Basic mapping reductions without using Turing machines

I have problems with the basics of mapping reductions. I can understand how to do reductions using a Turing machine, but without it, I get a little bit confused. For example: How do I do a mapping ...
3
votes
0answers
93 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
1answer
99 views

Equivalence of dfferent TM definitions

I stumbled upon these two defintions of a turing machine: http://www.cs.um.edu.mt/gordon.pace/Teaching/Complexity/CoursePage/Notes/chapter5.pdf http://scholar.harvard.edu/files/harrylewis/files/...
3
votes
1answer
140 views

Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

The title says it all, I think. We know there are universal Turing-machines that only use a binary alphabet. But who proved this first? Turing himself showed the existence of a universal Turing ...
2
votes
0answers
74 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
1answer
189 views

Alternative definitions of ZPP and probabilistic Turing Machines

There are two ways to define a probabilistic Turing Machine: A Turing Machine that can toss coins during its computation. A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is ...