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
1answer
44 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
70 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
1answer
26 views

Is there way to compare computing power used in two blockchains when every one of them is using different mathematical function as a Proof-of-Work?

If I am a Bitcoin node, I can evaluate two blockchains in terms of each one consisting of more Terahashes than the other and thus deduct which one is the "correct" one. There is impartial source of ...
1
vote
2answers
90 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
2answers
23 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 ...
0
votes
2answers
34 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
0answers
35 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
0answers
19 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 ...
4
votes
1answer
777 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
2
votes
2answers
143 views

The order of ε-transitions in NFA

I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want ...
1
vote
0answers
17 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
34 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 ...
0
votes
1answer
52 views

Parallel programming models: Why do OpenMP and MPI dominate?

In a lecture on HPC parallel programming (for CPUs) we discussed various models available from Pthreads to OpenMP to MPI and others like Charm++, X10, UPC, Chapel…. The main focus was clearly on the ...
3
votes
0answers
34 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
93 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, ...
3
votes
1answer
731 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 ...
0
votes
1answer
34 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 ...
-1
votes
1answer
33 views

Convert CFG to CNF Arithmatic Expression

Convert CFG to CNF The Grammar E→E+T E→T T→T*F T→F F→(E) F→x Step 1 Assign variables to terminals A→ + B→ * C→( D→ ) F→x ...
5
votes
3answers
1k views

How is the computational power of a human brain comparing to a turing machine?

This seems related to these questions at a glance: What are some problems which are easily solved by human brain but which would take more time computers? What would show a human mind is/is not ...
2
votes
1answer
118 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 ...
27
votes
7answers
5k views

Is there a physical analogy to the Turing Machine?

Recently in my CS class I've been introduced to the Turing Machine. After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine. I was ...
8
votes
1answer
143 views

Are weakly polynomial time algorithms truly polynomial?

I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia states an algorithm runs in strongly polynomial time if ...
8
votes
3answers
2k views

Differences between programming model and programming paradigm?

What is the relation and difference between a programming model and a programming paradigm? (especially when talking about the programming model and the programming paradigm for a programming language....
2
votes
2answers
465 views

Explanation for indirect addressing

While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump. ...
3
votes
2answers
179 views

If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack. But, a link of Show that { ...
1
vote
1answer
40 views

trace vs. computation vs. run vs. execution vs. walk

Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions. Does any work distinguish between these ...
1
vote
0answers
16 views

Which machine learning should I choose for a one->list relation

I'm trying to write machine learning software that will predict a list of 3 values from a given number input (reverse grayscale). There is a function determining values of the list to the grayscale, ...
11
votes
4answers
613 views

Why is the tape not part of the definition of a Turing Machine?

I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, ...
1
vote
1answer
101 views

Why no DPDA can accept Palindrome? (according to this proof)

This proof is from the book "Introduction to Languages and the Theory of Computation" by John C. Martin. My question is from the pink part at the second page: It follows in particular that no ...
0
votes
1answer
35 views

Would models of computation in other conceivable universes be Turing complete?

I'm interested in gathering some references that discuss the topic of the relationship between computation and physics. Specifically, I'm interested in investigating two points of view: our current ...
2
votes
0answers
30 views

How does one program in a tag system?

I've played with 2-tag systems a bit and read all about tag/lag systems. They're great for experimenting with computation, and obviously useful as intermediaries in various proofs. My question is: ...
0
votes
0answers
17 views

How to model most optimized encoding of string data

Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation. I ...
1
vote
0answers
32 views

Can differennt computation model lead to different complexity?

There are many examples where someone replaces a CPU with a GPU or an FPGA and get a performance boost of $\times 100$ or more, but is it possible for a change in the architecture of computational ...
5
votes
3answers
153 views

Is there any other computation theory besides the one in automata theory?

I'm a bit confused at a fundamental level. In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, ...
0
votes
0answers
9 views

Formal definiton of RAM model with D disks of blocks B, fast memory M and P processors

In some articles I've read of RAM model with D disks of blocks B, fast memory M and P processors. Is there a formal deifition of that model?
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 ...
0
votes
0answers
21 views

What is difference between a formal system and a model of computation

I don't exactly know the difference--partly because I cannot find a mathematical definition for a model of computation (also why is this)?
11
votes
3answers
520 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
1answer
30 views

Is “represents” a symmetric relation in the provided answer to TAOCP exercise 1.1.9?

In exercise 1.1.9 of volume 1 of The Art of Computer Programming, the reader is asked to formulate a set-theoretic definition for the concept "$C_2$ is a representation of $C_1$" where $C_1$ and $...
2
votes
0answers
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 ...
7
votes
3answers
5k 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?
2
votes
1answer
73 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 ...
0
votes
0answers
12 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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
32
votes
7answers
10k views

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
0
votes
1answer
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. ...
0
votes
0answers
29 views

Computational power of machine learning

In a nut shell, machine learning is a class of algorithms that can "train" data-structures. You provide a trainer with partial information, and it will produce some entity which can be queried on ...
3
votes
3answers
11k views

What is the difference between Babbage's analytical and difference engine?

What is the difference between Babbage's analytical and difference engine? Can they even be compared?
1
vote
1answer
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 ...

1
2 3 4 5
8