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
7
votes
0answers
87 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
56 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
40 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
1answer
86 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
24 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
347 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
38 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
96 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
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 ...
0
votes
0answers
47 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
2k 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
382 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 ...
7
votes
2answers
434 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
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, ...
3
votes
2answers
62 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
102 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
213 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
102 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
186 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
346 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
154 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\...
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?
1
vote
1answer
71 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
130 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
106 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
70 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 ...
4
votes
0answers
57 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
41 views

Alternatives to Sequential Computation

When software boils down to assembly, it is just a sequence of instructions like this: ...
3
votes
1answer
41 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
154 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
1k 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
79 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
46 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 ?
6
votes
1answer
877 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
88 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 ...
70
votes
6answers
15k 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
198 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
877 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, ...
2
votes
1answer
129 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 ...
3
votes
1answer
287 views

Understanding Applicative Evaluation Order with the Z-Combinator

I am trying to understand how the Z-combinator (Y-combinator for applicative order languages) definition came about. As Python is applicative I am using Python for this. So I know Python's evaluation ...
7
votes
2answers
1k views

$\lambda$-calculus, is there encoding of for or while?

In $\lambda$-calculus, we can encode arithmetic, numbers, booleans, and even compute factorials of numbers, as shown here. Is there encoding of "for" or "while"?
2
votes
2answers
330 views

Solve every problem with recursion [duplicate]

Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks
5
votes
3answers
263 views

Defining computable functions on arbitrary sets

Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to ...
0
votes
0answers
59 views

Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...
1
vote
0answers
76 views

Proof that the language is not regular (Pumping Lemma) [closed]

I have to prove that the following language is not regular: $$\{ x | x = 10^{2n} + 10^n + 1, n ≥ 1\}$$ I am trying to prove it using Pumping Lemma, however, when I expand the expression I have both ...
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 ...
2
votes
2answers
148 views

Time complexity of expanding decimal to new base

There is already a post on this topic on stackoverflow. Nevertheless, I am asking the question here again, primarily because I do not understand the answer given there, and also because I have some ...
2
votes
1answer
423 views

How $N$ qubits correspond to $2^N$ bits?

I read everywhere that $N$ qubits correspond to $2^N$ bits. Let's start with 1 qubit, which is commonly represented by $\alpha |0\rangle + \beta |1\rangle$ where alpha and beta are complex numbers. ...

1
2
3 4 5
8