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.

0
votes
0answers
36 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 ...
-5
votes
0answers
26 views

Evidence based research [closed]

Case Scenario The patient is a 77-year-old man admitted for dyspnea and fever. He fell ill 4 days ago with low￾grade fever, chills, myalgias, rhinorrhoea and a non-productive cough. One day ago he ...
4
votes
1answer
117 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
23 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
35 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
57 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
75 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
76 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
20 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 ...
1
vote
1answer
19 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 ...
2
votes
1answer
30 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
42 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
61 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
21 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
72 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
32 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
28 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
16 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
37 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
113 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
85 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
154 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
105 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
47 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
56 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
107 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
74 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
68 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
91 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
44 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
37 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
44 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
47 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
47 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
29 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
27 views

Alternatives to Sequential Computation

When software boils down to assembly, it is just a sequence of instructions like this: ...
2
votes
1answer
38 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
95 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
304 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
54 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
628 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 ...
0
votes
0answers
45 views

Variable bytes (bit arrays) and flipping single bits?

My interest is strictly theoretical at this point, but ultimately applied. Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ...
66
votes
6answers
14k views

Why is the Turing Machine a popular model of computation?

I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we ...
3
votes
1answer
56 views

What's the difference between transdichotomous model and RAM?

In Wikipedia, it says the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size. However, a random access machine ...
3
votes
1answer
419 views

Real life applications of finite automata

I have some confusion about the differences between finite & infinite. can someone tell me how the Toll machine or Park meter, soda vending machine can be used with infinite language? if not, ...
1
vote
0answers
73 views

What is the computation model of Prolog?

Several computation models have representative programming language counterparts, as, according to this answer, Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus, and ...
17
votes
8answers
7k views

Why can we assume an algorithm can be represented as a bit string?

I am starting read a book about Computational Complexity and Turing Machines. Here is quote: An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical ...