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
1
vote
1answer
36 views

Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory?

Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the ...
1
vote
1answer
35 views

Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer

Well in many texts and places I have seen a called statement, which claims it self to the famous "Church Turing Thesis". I have seen many texts say that based on Church-Turing Thesis : &...
0
votes
0answers
39 views

Chomsky Hierarchy of a Computational Model

I am interested in knowing the Chomsky hierarchy of a particular computation model. Also, I would like to know if it is equivalent to Finite State Machine or is Turing complete. This computation ...
-1
votes
0answers
18 views

Show that if A is context-free and B is regular, then A ÷ B is context-free [duplicate]

For languages A and B over Σ, define the language A ÷ B as follows: A ÷ B = {w ∈ Σ^∗: there exists x ∈ B such that wx ∈ A} Show that if A is context-free and B is regular, then A ÷ B is context-free.
0
votes
1answer
63 views

Is the following language regular; context-free but not regular; or not context-free?

Let $\Sigma=\{0, 1, \#\}$. Is the following language regular; context-free but not regular; or not context-free? Justify your answer $$L=\{x\#y :\ x, y \in\{0, 1\}^∗\text{ and }\operatorname{bin}(x) + ...
1
vote
0answers
10 views

About the paper Privacy-preserving in association rule mining using an improved discrete binary artificial bee colony

I don't understand two parts in this paper: The min notion on page 4 line 357 (equation 10d): I understand this as to find all the $M_{10}$, $M_{11}$, $M_{01}$ first and then try to minimize the ...
0
votes
0answers
23 views

Do Field separators delimit only fields or also data units inside fields?

At least intuitively, I understand the following terms to be rigorously associated: Field Separator (FS) as a delimiter which delimits text segments such as words, sentences or lines/fields and an ...
1
vote
1answer
17 views

Explanation of roofline model

I am currently studying the roofline model. Wikipedia [2] shows the following example graph: The diagonal line shows $\beta * I$. But I do not understand why this line does not go through the zero ...
1
vote
1answer
38 views

Complexity of inverting a diagonal matrix

What is the complexity of inverting a $n \times n$ diagonal matrix? From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its ...
0
votes
0answers
35 views

Are there words without fixed size length?

Here, Yuval Filmus wrote: Unary encoding is only relevant in contexts where the length is not fixed. Are there words without fixed size length? Is there a Computer Science theory which describes ...
0
votes
1answer
48 views

EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we ...
0
votes
0answers
33 views

On the queue automaton and acceptance of this language

We have this language: $$ L = \{𝑥𝑥^r|𝑥∈Σ^∗\} $$ We want to show that it can be accepted by QA. consider a letter like #, before anything we push it to the queue. using this additional letter, we ...
0
votes
0answers
13 views

Verification of atomic primitives using Petri Net Models

I want to verify semantics of a library of atomic primitives that I wrote. The idea is, only if the semantics of all the primitives are consistent with each other, an application that uses them could ...
1
vote
0answers
52 views

Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?

I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational ...
0
votes
0answers
15 views

What the the most efficient and effective VM ISA/computational model format backed by research?

The JVM and CLR are stack based machine are very efficient, mainly due to the investment in these platforms than an efficiency and effectiveness of stack based VMs. For en entity that does not have ...
2
votes
0answers
26 views

Generalizing Quantum Computation

When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to ...
1
vote
1answer
29 views

What is the language of Sigma^n? Confused about meanining

I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet? Thank you so much!
2
votes
1answer
39 views

Programming languages and Model of computations

I am learning about model of computation and I found this wikipedia entry that categorises and outlines various model of computation. Now I want to know the programming languages that builds on these ...
0
votes
0answers
45 views

What is the difference between type theory and logic programming (in terms of declarative programming and specification)

How is does type theory (coq, lean, agda), and logic programming (prolog, datalog) differ from each other. Logic programming is a way of declarative specifying an algorithm, using classical 1st order ...
1
vote
0answers
16 views

Computational Model for learning Computability and Complexity

I was reading the book by Kozen-Theory of Computation. There is a statement that Turing machine is the best model for defining basic time and space complexity because atleast for higher levels of ...
0
votes
0answers
72 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
2
votes
0answers
54 views

Restrictions on Computational Methods (Art of Computer Programming)

In the Art of Computer Programming, Knuth describes a computational method as a quadruple $(Q, I, \Omega, f)$ where $I, \Omega \subseteq Q$, $\Omega$ is pointwise fixed, and each $x \in I$ defines a ...
0
votes
0answers
21 views

Power of Multi Tape and Multi Track Turing Machine

How can we prove that the computational power of Multi Track and Multi Tape Turing Machine is same as the Normal or Standard ( One Tape- One Track- One Head) Turing Machine?
0
votes
0answers
36 views

Context-Free Grammar Question

Given a regular Expression: 0^a 1^b 0^c, where a+b=c and a,b,c >= 0. Find the cfg for this expression. Here is what I tried to do: s -> AsB A -> 01 B -> 0 But then a language could be ...
0
votes
1answer
45 views

Black-Box Machine

Suppose we have mysterious machine which return median $m$ of given set $S$ and set $S/\{m\}$ in constant time, where $S/\{m\}$ denotes the difference of $S$ and element $m$. Prove that we can sort ...
4
votes
1answer
82 views

A language that is not context free

I working through some textbook exercises, and came across a problem that I'm struggling with. Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL. I've got the idea ...
1
vote
1answer
111 views

Empirical Risk and True Risk - Generalization Error Proof

I showed that, over an uncountable domain,learner A and a distribution P, such that for every sample size m and all samples S from $P^m$ $$ : L_S(A(S)) − L_P (A(S))| = 1 $$ Now I wanna prove for ...
1
vote
1answer
35 views

Regularity of a language constructed from a know regular language

I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language: $$ \{x|\...
3
votes
3answers
174 views

What motivates the RAM model?

It looks like most of today's algorithm analysis is done in models with constant-time random access, such as the word RAM model. I don't know much about physics but from popular sources I've heard ...
0
votes
2answers
246 views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
1
vote
0answers
55 views

If $A\in RE $ then $f(A)\in RE$

Let $A\in RE$, and define$f(A) = \{y |\ y= f(x),\ x\in A\}$ for some computable function $f$. Then $f(A)\in RE$. I can't figure out why this is true. Since $f$ is computable there is a Turing machine ...
1
vote
0answers
119 views

How design a Deterministic finite automata which accept string starting with 101 and how to draw transition table for it if there is a dead state

I’m trying to design a DFA which accept string starting with 101 if the string start with 0 then it goes to dead state.Is my design is correct or wrong? And I don’t know how to draw transition table ...
0
votes
1answer
183 views

Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite

Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:...
0
votes
1answer
20 views

Do we have to calculate time for declaring statement in RAM model?

Do we have to calculate time for declaring statement, in my case int num3 statement. The following question was asked by professor as a post-lecture quiz. I ...
-1
votes
1answer
266 views

turing machine accepting language {ww} has ω($n^2$)

prove or disprove that any turing machine which accepts language $l=\{ww | w ∈ \{0, 1\}∗ \}$ has time complexity $ω(n^2)$
0
votes
0answers
58 views

Convert PDA by final state in to cfg

Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
0
votes
0answers
21 views

Mealy machine and moore machine

Can we compute the number of machine of two kind of transducers (mealy and moore) with $n$ states, and lenght of input symbols $m$, and lenght of output symbols $p$.
0
votes
2answers
22 views

Equivalence between a TM and a changing TM

Let a changing TM be a TM which is not able to write the same symbol which is being read. Formal: $M^*=(Q,\Sigma,\Gamma,\delta,q_{accept},q_{reject})$,$\delta(q,a)=(q^*,a^*,c),a \neq a^*$ with $q,q^...
2
votes
1answer
79 views

Expressing functions using the arithmetic dictionary

i have seen in the "logic to cs" class i take - a theorem that states: "every recursive (computable) function $f$ can be expressed using the arithmetic dictionary {$C_0, C_1, f_+(,), f_x(,), R_\le(,)$}...
2
votes
1answer
82 views

What does Lambda Calculus teach us about data?

In Lambda Calculus, the distinction between data and code doesn't seem to exist. Is there something fundamental about this, or purely Lambda Calculus's thing? Some context: as a software developer, I ...
0
votes
2answers
66 views

How to find optimal partition subsets

Given a partition $[0,1]$,there are 5000 partition subsets $P_i=[a_{i1},a_{i2}]\in[0,1], 0≤a_{i1}\leq a_{i2} \leq 1, i \in \{1,2,...,5000\}$. I want to analyze these subsets and find 10 subsets to ...
1
vote
2answers
873 views

Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
1
vote
0answers
39 views

Are there non-quantum, (potentially) realizable in the real world models of computation that allow a polynomial speedup over RAM?

I hear a lot about how quantum computers are a big thing because they allow solving some problems in polynomial time which we don't know how to do classically. As far as I understand it still isn't ...
1
vote
2answers
93 views

Proof that uniform circuit families can efficiently simulate a Turing Machine

Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity ...
1
vote
0answers
25 views

Is it semidecidable to test whether a Turing decidable language is empty?

I'm not sure how to go about solving this. I tried this: Suppose L is a Turing decidable language. Turing Machine M1 is a decider of L and M2 is a decider of the complement L We construct a TM U ...
1
vote
0answers
18 views

Is there a recursive problem encoding the Turing completeness of a model of computation?

Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. ...
0
votes
1answer
44 views

Closure on regular languages

A) Let $L$ be a regular language. according to the theorem there is an DFA which accepts the language. Describe shortly how to change the DFA to NFA which Accepts $L^R$, where R is reverse. There is ...
3
votes
0answers
42 views

Is there an abstract architecture equivalent to Von Neumann's for Lambda expressions?

In other words, was a physical implementation modelling lambda calculus (so not built on top of a Von Neumann machine) ever devised? Even if just on paper? If there was, what was it? Did we make use ...
2
votes
1answer
133 views

Computational complexity of counting symbols

Consider the counting function $\{x\}^* \rightarrow \mathbb N$ that counts the number of occurrences of the symbol $x$. I am confused about the (asymptotic) complexity of computing this function, ...
2
votes
1answer
501 views

Does Turing machine have no shift?

In a Turing machine I read that it can go only right or to left. But in my book [elements of theory of computation, Book by Christos Papadimitriou and Harry R. Lewis ] it says that Turing machine ...

1
2 3 4 5
9