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

410 questions
Filter by
Sorted by
Tagged with
25 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|\...
146 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 ...
62 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 ...
53 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 ...
35 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 ...
32 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$:...
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 ...
49 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)$
14 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 ...
18 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$.
20 views

20 views

### Similarities between Babbage's difference engine and the Turing machine

What would you consider similarities between the difference engine and the Turing machine? At this point I feel I know how they both function, yet I can't point out any worthwhile similarities between ...
39 views

### support vector machine values

Does anybody knows how to calculate w1 and w2 and b . I have the formula but I have no idea where those numbers come from . my question has solution so it is not a home work because the solution of ...
81 views

### Showing the following language is decidable

Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable. Generally such questions seem to be ...
15 views

### Turing: Are the “m-configurations” in his original paper the same as the “means” in his definition of his “computable”?

Are Turing's "m-configurations" the same as the "means" in his original definition of "computable"? In the first line of Turing's paper "On Computable Numbers...", he defines a "computable" number as ...
23 views

### Complexity classes for various models of computation

The various complexity classes usually taught and studied ($P$, $NP$ $co-NP$, EXP, NSPACE etc) are usually defined using Turing Machines as the preferred model of computation. Are these sets of ...
28 views

### Manage event programming under a stack-oriented language

I wonder how events, or more broadly reactive programming, could be managed in a simple stack-oriented language. For example, let's imagine a context where there is a button that displays a small ...
35 views

### Is the graph symbol used in dask a general notation?

Dask is a flexible library for parallel computing in Python. This piece of code define some simple functions. ...
35 views

### Injectivity verification in o(n) space and O(n) time

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
67 views

### If the human brain is a Turing machine then how is it able to ascertain that certain problems are undecidable? [closed]

I recently read about the idea that the human brain might be a Turing machine (or Turing complete). If that is true then how is the brain able to reason that a certain problem is undecidable for e.g. ...
28 views

### why does the pumping lemma want us to only consider the first repitition of states?

In Sipser's Intro to Theory and computation, He writes: I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
801 views

### Difference between multi-tape Turing machine and single tape machine

A beginner's question about "fine-grained" computational power. Let $M_k$ be a $k$-tapes turing machine, and let $M$ be a single tape turing machine. We know that $M_k$ and $M$ both have the same "...