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
2
votes
0answers
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 ...
4
votes
2answers
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 ...
-1
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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.
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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. ...
0
votes
1answer
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 ...
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
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 ...
1
vote
2answers
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,...
2
votes
1answer
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 ...
1
vote
1answer
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. ...
1
vote
1answer
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) (...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
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 ...
5
votes
1answer
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 ...
0
votes
4answers
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": ...
2
votes
1answer
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 ...
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
66 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
146 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
147 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
3k 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
81 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
97 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
119 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
158 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
82 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
285 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 ...
4
votes
0answers
62 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
1answer
95 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
275 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-...
13
votes
1answer
393 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
127 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
94 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
129 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
1k 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
1k 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
237 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 ...
6
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
333 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 ...
38
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
627 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 ...
4
votes
0answers
136 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
427 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\...

1 2
3
4 5
8