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
0
votes
0answers
4 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
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
31 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 ...
2
votes
0answers
30 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
81 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
78 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 ...
0
votes
1answer
37 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
2answers
165 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 { ...
8
votes
1answer
126 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 ...
1
vote
1answer
37 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
votes
1answer
27 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 ...
1
vote
0answers
15 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, ...
0
votes
1answer
34 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
24 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
16 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
1answer
80 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 ...
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 ...
0
votes
0answers
8 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
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)?
1
vote
1answer
29 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 ...
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 ...
2
votes
1answer
52 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
11 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 ...
0
votes
1answer
33 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 ...
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
votes
1answer
61 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. ...
0
votes
0answers
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 ...
2
votes
1answer
625 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 "...
3
votes
1answer
44 views

Uncomputably coded model of computation

There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there ...
0
votes
0answers
15 views

State-machine semantics of instruction set architectures

An instruction set architecture is an abstraction, a common interface layer between the software and the micro-architecture. The existence of this clearly delineated interface is becoming increasingly ...
1
vote
0answers
31 views

Theory for programs that are “embedded” in other programs?

We can make the following distinctions: (I will use the term "program" and "machine" as synonyms). A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes ...
0
votes
1answer
212 views

What's the purpose of the non-deterministic Turing machine?

(*) Acronyms NTDM := non-deterministic Turing machine. TM := deterministic Turing machine. (*) Consider the following idea The NTDM is able to follow, in parallel, all paths of the tree of the ...
2
votes
2answers
114 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 ...
29
votes
4answers
4k views

What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?

I encountered below statement by Alan M. Turing here: "The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are ...
0
votes
0answers
20 views

Can we use Wifi signals readings to estimate 3D shapes?

I don't know if this is the appropriate SE for this question, but I hope someone would answer !
0
votes
0answers
28 views

Is the proof for the undecidability of $A_{TM}$ still valid if we change certain parts?

i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book). on page ...
1
vote
0answers
26 views

General notion of memory for a computational model

I have just started studying Michael Sipser's Theory of Computation, studying various computational models such as FAs, PDAs et cetera. In the book, the term "memory" was often used,as in the case of ...
4
votes
1answer
255 views

Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle

On a parallel machine with $n$ processors we can compute the sum (or product, or the result of any associative operation) on $n$ numbers in $\log n$ steps. In the first step combine neighbors to get $...
2
votes
1answer
39 views

What is the motivation behind “ Descriptive Complexity ”?

Time and Space are two commons parameters (and also natural parameters) to measure the complexity of the problem. I am not able to understand the motivation behind defining " Descriptive Complexity". ...
2
votes
1answer
40 views

Examples of logic gates using non-standard models

These are the only ones I have been able to find online: Pulley Logic Gates Marble adding machine MARBLE COMPUTER LOGICAL AND GATE I would like to find some more discrete models like these (as ...
1
vote
2answers
77 views

Would any continuous model of the universe have/be based on hypercomputational laws?

I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that: "The universe ...
0
votes
1answer
215 views

Is arithmetic turing complete?

Maybe my question doesn't make sense, because I lack some more thorough understanding, but I was curious if arithmetic was Turing complete? As I understand it, a "model of computation" is a mechanism ...
7
votes
0answers
84 views

Automata that is Turing complete if you add a nondeterminism

Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
0
votes
0answers
52 views

What is “Phrase structure grammar”?

I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar: Type-0 grammars generate recursively enumerable languages. The ...
0
votes
1answer
24 views

Numbering of vertices in RAM model

I have read few research papers in which given a graph $G$ where $V$ denotes its vertex set and $E$ denotes its edge set. Model of computation is word RAM. "Without loss of generality assume that ...
1
vote
1answer
38 views

What is the motivation behind restore model of computation?

The memory that stores the input is called the input memory. The memory that an algorithm additionally occupies during the computation is called the working memory. $\textit{Model of Computations}$ ...

1
2 3 4 5
8