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
0 answers
23 views

Create a Turing machine for this interactive game

Given two players $A, B$ and some natural number $n \ge 2$, let $\#(A,B,n)$ denote the following algorithm: $A$ thinks of some number $a \in \{1,\ldots,n\}$ Until the game ends: $B$ thinks of some ...
1 vote
1 answer
86 views

Time Complexity of Exponentiation Operation as per RAM Model of Computation

Now, $\color{blue}{\text{Exponentiation}}$ is defined as Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and ...
45 votes
7 answers
11k views

Is there anything that MUST be done on a multi-core CPU?

When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing ...
0 votes
1 answer
19 views

Transition System vs State Machines

Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (...
2 votes
0 answers
34 views

Belt-based mechanical computers

I've seen a lot of mechanical computers based on gears and rigid rods, but none so far that consequently use belts (not chains) for transmission of information. Belts allow for easy negation (by ...
0 votes
2 answers
50 views

If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?

The concept of reducibility in computability theory is very confusing for me. For example, as described in Micheal Sipser's Introduction to the theory of computation, I understand that if language A ...
0 votes
1 answer
20 views

Is it correct to perform feature distillation when both the teacher and student model architectures are completely different

When the architectures of the teacher and student networks do not just vary by network depths but are completely different, is it logically correct to distill knowledge at feature level (say from ...
1 vote
1 answer
38 views

Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous

Question: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous. The CFG is as follows. $G = (V:=\{E,T,F\}, \Sigma:=\{+, \times,(,),x\},R,E\})$ where $R$ consists of 6 rules: $E\...
0 votes
1 answer
24 views

Prove that the grammar $S\rightarrow (S)|SS|\epsilon$ generates precisely all well-balances parentheses

Question: prove that the grammar $G = (\{S\}, \{(,)\}, R, S)$ where $R$ consists of three rules: $S \rightarrow (S)~|~SS~|~\epsilon$ generates precisely all well-balanced parentheses. I found a source ...
0 votes
1 answer
13 views

Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular (without using complement closure)

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$ (without using the complement closure property). My thoughts: I understand ...
0 votes
1 answer
34 views

Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$. My thoughts: I understand that $L_2 = \{0^n1^n: n\geq 0\}$ can be shown to be ...
3 votes
0 answers
61 views

Are there any other useful computational architectures than von Neuman based ones?

As far as I understand it, computation today is largely based on Turing machines implemented in von Neuman architectures. Are there other realizations of Turing machines in use or being considered ...
24 votes
3 answers
3k views

Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent: if array access is really $\Theta(1)$, this means ...
4 votes
0 answers
189 views

What is the computational class of a reduced Wang B-machine?

A Wang B-machine is Turing-complete and has only 4 instructions: right: Move head right. left: Move head left. ...
2 votes
1 answer
43 views

Simulating nondeterministic RAM with nondeterminstic turing machine

Nondeterminstic RAM is like deterministic RAM with extra instruction “JMAYBE” which nondeterministically jump or continue when executed. According to this paper: An $O(T \log T)$ reduction from RAM ...
1 vote
1 answer
62 views

Is there a way to compare computing work spent 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 ...
2 votes
2 answers
270 views

The class of problems that can be solved efficiently using physical means?

By "physical means", I mean, for example, using water pouring down tubes, or combining chemicals, etc. Basically, using some experiment in the physical world to perform some computation. I'...
1 vote
0 answers
22 views

What are practical applications for markovs algorithm(string rewriting systems)

:) Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
7 votes
6 answers
2k 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
1 answer
51 views

Solving efficiently NP problems with infinite precision

I heard a few times that if we allow computations with infinite precision, we could have unrealistic powers of computation up to the point of solving NP problems efficiently. Is it true? If yes: what ...
0 votes
1 answer
27 views

Verification of atomic primitives using Petri Net Models

I want to verify semantics of a library of atomic primitives that I wrote. The idea is, only if the semantics of all the primitives are consistent with each other, an application that uses them could ...
0 votes
2 answers
862 views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
1 vote
8 answers
486 views

Is infinitely fast computer fundamentally impossible even theoretically?

This may get slightly philosophical, but consider the following program: ...
2 votes
0 answers
31 views

Universal register machine that recognizes the image of a partial function

Suppose $f$ is a $\mathbb N$-valued partial function over a subset of $\mathbb N$. If $f$ is computable by a universal register machine program, is the constant partial function $$ g:\text{image}(f)\...
2 votes
1 answer
72 views

prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

Given that $\#\notin \Sigma$ and $L\subseteq \Sigma^*\#\Sigma^*$, prove that if $L$ is context-free language then $L' = \{w_2\#w_1 \mid w_1\#w_2\in L\}$ is context-free. I'm trying to prove this in ...
1 vote
1 answer
65 views

A decidable language that can't be decided by a circuit ensemble of linear size

Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
0 votes
0 answers
19 views

Where are some examples of unsatisfiable formulas? Especially about 3CNF paradigm

I've been learning co-NP recently. I know that UNSAT $\in$ co-NP. So I want to find more examples of UNSAT, especially about 3CNF paradigm.
2 votes
2 answers
90 views

Is ε a part of alphabet or property of alphabet and NFA in FA

I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following: 3rd point of the above image is the ...
0 votes
1 answer
27 views

How to represent mutually exclusive events in CSP

I am studying Communicating Sequential Processes (CSP), and I understand that an event can be "emmited" ($\overline{e}$) and an event can be "waited on" ($e$), so that an event ...
0 votes
1 answer
46 views

Build a 2-PDA for language accepted by Turing Machine

I saw this question on the internet and found many solutions actually but none of them really persuade me that much. Question: Given language $L$ which is accepted by a Turing machine $M$, provide a 2-...
2 votes
1 answer
56 views

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$ Here is what I have tried: 1. Starting State Read $a$, Write $x$, Move Right, Go To 2 Read $x$, Write $x$, Move Right, Go To 1 Read <...
0 votes
0 answers
23 views

What is the computational class of neural networks?

What is the relationship between formal automata and the different types of neural networks? What kind of neural network would you need to be able to parse context-sensitive languages, for instance?
1 vote
1 answer
32 views

Why are reachability trees meaningful for Petri Nets

To construct a reachability tree we start with the initial marking and then consider all enabled transitions and fire them one by one. That is, we find the marking corresponding to firing each. I can'...
5 votes
2 answers
122 views

Do all Turing-complete programming languages have to contain infinite loops?

Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below: Conjecture. There does not exist a set $...
12 votes
8 answers
2k views

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

I wish there were more, but the subject pretty much captures my whole question. Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...
2 votes
0 answers
50 views

Differences between a computation model and an abstract data type

I am wondering about the difference between an abstract data type (ADT) and a computation model. As I understand them: A computation model defines the basic unit of computation, that is, what can be ...
8 votes
3 answers
6k 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
1 answer
85 views

Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?

I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational ...
0 votes
0 answers
41 views

In search for a complete definition for write-only TMs / Tapes

In the following lines I will present my question, whose content is divided in two parts: Preparation and Actual . (1) — Preparation Regarding the formal definition of the (one tape) general Turing ...
1 vote
0 answers
54 views

Confused about the concept of deciding in nondeterministic Turing machines

I read this discussion before. However i’m still confused. I used to think a language decided by a NTM if for every input $w$ in $\Sigma^*$, all of the branches in computation tree leads to a halting ...
0 votes
0 answers
26 views

Why do we promote Ubiquitous Computing when there are problems out there that cannot be solved computationally?

According to Alan Turing, there are 2 types of problems i.e. NP Complete and non-NP Complete, then why do we promote Ubiquitous Computing and introducing sensors and embedded systems into our daily ...
8 votes
2 answers
2k views

What is the difference between quantum computing and parallel computing?

Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the ...
2 votes
1 answer
42 views

Is there a non PSPACE language s.t exponential padding of it is PSPACE?

I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that: Is there a language $ L \notin PSPACE $ over the alphabet {0,1} ...
-1 votes
2 answers
50 views

Are there infinitely many distinct implementations of any algorithm using any Turing-complete computational model?

Subject pretty much says it all. My strong impression is that for any algorithm and any choice of programming language or computational model, if it's Turing-complete, then there must be infinitely ...
3 votes
1 answer
711 views

λ-Calculus extensions: meaning of extension symbols

When working with λ-Calculus I see lots of extensions that use other symbols such as ∀ <:Top {} ←, which are from "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce. ...
1 vote
2 answers
58 views

Does multiplying word size numbers take constant time?

Does multiplying word size numbers (using standard grade school algorithm) take constant time? Can you use this to speed up computation and do the fast multiplication algorithms use this? By constant ...
1 vote
1 answer
52 views

Efficient comparison, using only sum, product, difference, and conditional jump if zero

I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
0 votes
0 answers
22 views

Is a computational model that can instantly access any storage address and can access any arbitrary number of them at once more powerful then a TM?

This would be a computational model that would have unbounded space. But with a jump command that can access and do operations on any finite number of cells at once. Actual calculations would take ...
0 votes
3 answers
45 views

For 3CNF unsatisfiable boolean formulas, does it take exponential time to transform them into disjunctive form?

From the link Solving SAT by converting to disjunctive normal form, I learnt that the algorithm to transform any boolean formula to disjunctive form takes exponential time in worst case. But I have a ...
0 votes
0 answers
77 views

Why EQ(cfg) is undecidable language?

I was studying Theory of Computation and I learned that EQ(cfg)[where the input is G1 and G2 both are CFGs and L(G1) = L(G2)] is undecidable but didn't understand why? Can you please explain it to me?

1
2 3 4 5
10