Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
26 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
57 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
1answer
41 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 ...
28
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
25 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
24 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 ...
0
votes
0answers
60 views

RAM and Turing machines: time complexity of simulation

My RAM machine is very simple: it has $k$ tapes, an input tape and one special control tape it has an infinite memory (array called $A$) which can be accessed randomly the control tape is read ...
4
votes
1answer
209 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
30 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
38 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
61 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
91 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
77 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
27 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
21 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
32 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}$ ...
0
votes
0answers
52 views

Correctness proof: induction on sequence of steps, need a stronger claim?

Im trying to prove the correctness of the construction proposed in this site answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we can ...
0
votes
1answer
71 views

Why a TM with infinite states can decide the halting problem?

Assuming we have a model of TM with an infinite number of states. The domain and range of the transition function are also infinite. Given a description of a TM $M$ and a string $w$ how can we use the ...
0
votes
1answer
22 views

Can all Turing-computable problems be solved with a machine with finite tape and infinite controls?

We know all computer computable problems can be solved using the infinite tape and finite control system of the turing machine. Now think something different, let the tape is finite but the control ...
2
votes
0answers
87 views

Equivalence between different Turing Machines and a definition of simulation

Im having some difficulty understanding how the following two concepts could be related. Equivalence between TMs as is commonly tought According to this site answer, to prove a standard TM model to ...
2
votes
0answers
36 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
1
vote
0answers
46 views

RO turing machine with finite memory

Consider the following: A weak TM is a TM with finite tape in size $k$ which can only read its input values. note: the tape size does not include the input length. I need to determine whether if the ...
0
votes
0answers
18 views

How to prove that models of indirect and direct RAM machines are equivalent?

as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
0
votes
1answer
16 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 ...
0
votes
0answers
38 views

Is there a common unit of measurement for comparison of computing power used to solve mathematical puzzles?

I just wanted to make sure if I'm reasoning correctly. So, if two computers are solving the same mathematical puzzle i.e. SHA-256 function of Bitcoin (finding nonce that satisfies difficulty target), ...
-1
votes
3answers
328 views

why can not NPDA is equal to DPDA?

I have recently read that turing machine can be remodeled to perform as PDA now, i have a question that since DTM = NDTM ( non deterministic Turing machine) then every DTM can remodeled to be NDTM ...
2
votes
0answers
140 views

What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
5
votes
2answers
175 views

Why do DFAs with a single final state have less power?

I came across this question in a test and I had to answer whether it is true or false. DFA with single final state has the same powers as DFA with more than one final state. I was confused by what ...
5
votes
2answers
112 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, ...
3
votes
2answers
50 views

Weaker, but similar conditions to Turing completeness?

A model of computation is called Turing complete if it can simulate any Turing machine. This rules out for example a combinational logic circuit. However, there is a sense in which combinational ...
3
votes
2answers
63 views

Primitive recursive plus Ackermann

Let us consider the class $\cal F$ of functions that contains all constant functions all projections the successor function the Ackermann function as basic functions, and that is closed under ...
1
vote
2answers
128 views

Can I program a universal Turing machine to accept arbitrary input encodings?

I've been reading about building Turing machines for specific purposes, and some sources talk about input encodings and some talk about programming specific machines, but I've been unable to find ...
1
vote
1answer
75 views

SIMD computational model

Flynn's taxonomy contains three interesting computer architectures: SISD, SIMD, MIMD. For the SISD architecture, we have RAM computational model that simulate real SISD systems very well; For the ...
2
votes
2answers
72 views

Is this system Turing complete?

I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries. I came up with the ...
0
votes
1answer
134 views

What is the definition of computable partial function?

Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input ...
1
vote
1answer
55 views

Proving the equivalence of two definitions of NFA acceptance

Recall that an NFA $N = (Q,\Sigma,\delta,S,F)$ accepts $w=w_1w_2\ldots w_n$, where $w_i \in \Sigma$, if one of the following holds: (a) $\hat\delta(S,w) \cap F \neq \emptyset$, where $\hat\delta\...
6
votes
3answers
3k 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?
1
vote
1answer
43 views

Is there a model of computation based on discrete event dynamic systems?

I asked a question here about discrete event dynamic systems. They are systems whose state evolution depends on asynchronous events. It can be combined with flow to produce a hybrid system. There ...
0
votes
1answer
50 views

Definition of “overhead”

I am writing a paper on the invariance thesis introduced by Cees F. Slot and Peter van Emde Boas as; 'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and ...
1
vote
1answer
56 views

Point and Application of Recursive and Recursive Enumerable Languages

What is the point and application of recursive and recursive enumerable languages. Finite Automaton is used for pattern matching, designing computer architecture and protocols, CFG is used for ...
1
vote
2answers
56 views

Are all computational complexity results oracle results?

When talking about the complexity of a given operation, say multiplication of numbers, one usually counts the number of "elementary operations" that are required. For example, a common argument says ...
2
votes
0answers
31 views

The cost of memory allocation on the (tacitly assumed) Word RAM machine?

Consider a particular algorithm that solves the binary search problem (or similar stuff) by performing $\sqrt{n}$ simple operations on numbers of $\log(n)$ bits. Suppose this algorithm works on a <...
1
vote
0answers
30 views

Alternatives to Sequential Computation

When software boils down to assembly, it is just a sequence of instructions like this: ...
2
votes
1answer
39 views

Potential General Model of Computation with Physics?

I posted a question about a month back regarding the significance of Turing machines (relative to other models of computation). In that post, I mentioned vaguely some conversion between an input ...
0
votes
1answer
99 views

What are the general applications of Computer Science in the field of Psychology?

I am keenly interested to do a project in Computer Science that can aid to address the problems in the field of Psychology. Now I want to know what are the most general and research-oriented issues or ...
-1
votes
1answer
480 views

PCP is decidable over the unary alphabet

Show that the Post Correspondence Problem (PCP) is decidable over the unary alphabet ? = {0}.
1
vote
1answer
55 views

An axiomatic theory of computational models?

There are many different computational models, e.g. Turing machines, register machines, lambda calculus, etc. I am wondering if there exists an axiomatization of computation, that abstracts away ...
-1
votes
2answers
41 views

do the ram lose what it remembers when the power if cut off?

after shutting down the computer do the ram loses what it remember ? if yes is there some technics that are used to get what is stocked into the ram after shutting down the computer ?
4
votes
1answer
671 views

Do “Type-2” Turing machines with infinite length inputs have more computational power?

Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of ...