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.
490
questions
1
vote
0
answers
47
views
Can FFT for prime $n$ be implemented as a product of $O(n\log(n))$ $2\times 2$ unitaries?
Consider normalized DFT (discrete Fourier transform) — a transform with input $x = (x_0,\dots,x_{n-1})$ and output $y=(y_0,\dots,y_{n-1})$ s.t.
$$y_j = \frac1{\sqrt{n}} \sum_{l=0}^{n-1} x_l \omega^{jl}...
- 111
0
votes
0
answers
18
views
Why Random Access Machine could only have $N \leq 2^{W}$ memory slots? Is it general theorem of informal rule?
Here:
$W$ is "bitness" - number of bits in one machine word, that could be stored in memory slots
$N$ - number of memory slots (each has bitness equals $W$)
My solution:
If max length of ...
-6
votes
1
answer
51
views
Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?
I asked ChatGPT to give me the difference between unrecognizable and undecidable languages, and this what it gave me:
Unrecognizable languages can be accepted by a Turing machine, but the machine may ...
- 11
0
votes
0
answers
14
views
Computational power of Turing machines vs circuit ensemble
Is it true that for every Turing machine 𝑀, there exists a circuit ensemble 𝐶 such that 𝐿(𝑀) = 𝐿(𝐶), or is it true that for every circuit ensemble 𝐶, there exists a Turing machine 𝑀 such that �...
0
votes
2
answers
96
views
Why is the Turing machine model relevant?
I am learning about computational models, I wonder why Turing chose his model of Turing machines (the strip with the head and Read / Move left or right / Change state).
I am suspecting his physical ...
- 101
0
votes
0
answers
35
views
Creating a Turing machine for Substring and Equal String
How should I go about creating a single-tape Turing machine for the following language:
$$
x_{1,2} = \bigl\{ (a\#b) \mid (a,b) \in \{0,1\}^* \text{and a is a substring of b or a is equal to b} \bigl\}...
- 1
1
vote
0
answers
37
views
Seeking Intuitions about Recursion, Y Combinator and System F
So, as I understand things, System F (polymorphic lambda calculus) doesn't have the Y Combinator and isn't Turing Complete, but it is very expressive. This answer (https://cstheory.stackexchange.com/...
- 11
0
votes
0
answers
20
views
Proving a language is recursively enumerable
Prove that the following language is recursively enumerable:
L = {<M,x> | Turing machine M enters the same configuration twice on input x}
I have tried to construct a TM that maintains the ...
- 23
0
votes
0
answers
31
views
Proving existence of NFA with specific amount of vertices
For every $i$ we define $\Sigma_i=${$1, 2, ..., i$} and a language over said $\Sigma_i$:
$L_i=${$w\in \Sigma_i^*| \exists \sigma \in \Sigma_i :\sigma$ does not appear in $w$}
And I'm asked to prove ...
- 315
1
vote
1
answer
116
views
Product Construction for DFAs with different alphabets
How would you modify the Product Construction for DFAs to find a DFA that recognises the union of two regular languages with different alphabets. I am not looking for a way of finding an NFA then ...
- 23
0
votes
1
answer
39
views
For random-access Turing machines, is a pointer an arbitrary-length integer?
(Sorry for my previous ill-posed question; I deleted it. This question is a refinement.)
For every computer we use, it has finite RAM. In perspective of complexity theory, it's one giant memory that ...
- 313
0
votes
0
answers
20
views
Enumerating Turing Machine (a,b)*
What does it mean to make an enumerating Turing machine of (a,b)*, since it has so many possibilities as to what the string can be. Do I just pick some random string and enumerate it like aab?
- 1
1
vote
0
answers
9
views
Can a CAM-style abstract machine fold a tree? What if it has a second stack?
The title's a little provocative, sorry. In the categorical abstract machines (CAMs), technically there are no "right folds"; the only way to consume a list is from the "left" or &...
- 220
-2
votes
1
answer
42
views
Is it true to say that machine languages have some degree of abstraction?
I think anyone would agree that assembly languages ("threshold languages") have some very little abstraction but is it true to say that also machine languages have some degree of abstraction?...
- 1
1
vote
1
answer
150
views
Why NP is not certain subset in P/poly?
Complexity class P/poly includes languages, which cannot be calculated by means of classic Turing machine, including unary halting problem
However, class NP is relatively simple, can be calculated via ...
- 113
0
votes
1
answer
55
views
Is there a typo in this excerpt from the book?
Michael Sipser's Introduction to Theory of Computation:
Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a ...
- 51
0
votes
0
answers
53
views
prove that Every DPDA has an equivalent DPDA that always reads the entire input string
I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
- 1
1
vote
0
answers
52
views
What is the formal definition of a combinational logic?
Question Background
A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35):
The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
- 111
1
vote
0
answers
39
views
What is a "universal" cellular automaton exactly, what does it look like to compute "anything"?
About a Universal Computer, this wiki says:
A universal computer in a cellular automaton is a system that can compute anything that a Turing machine can compute (another term for this is Turing-...
- 2,163
0
votes
1
answer
193
views
Confusion regarding the intuition behind epsilon transition in NFA
I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )
Let's use this E-NFA as an example
My question is, do we ...
- 305
0
votes
2
answers
57
views
Why is Rule 110 considered "weakly" universal?
My supposition is that this is was more or less an automatic designation based on the fact that Rule 110 requires an infinite "background tiling" of the 14-bit sequence ...
- 284
0
votes
1
answer
39
views
what is the difference between triple sat and 3Sat?
I am trying to grasp the concept of triple sat compared to 3Sat. I understand that 3Sat has 3 literals for each for each clause. ${Triple-Sat} = \{ \phi | \phi $ has at least three satisfying ...
- 1
2
votes
3
answers
1k
views
Storing N bits on the smallest possible space in a real computer
Update. Since my original question was misunderstood by many, and lead to a lot of debate about various issues, let me try to pose this modified and rephrased question:
Assume that I have a computer ...
- 260
0
votes
1
answer
40
views
Models of computation less powerful than DFA
I wonder if there are "standard" models of computation that are less powerful than DFA that are still "mathematically interesting"? It is evident that restricting the set of DFAs ...
- 101
0
votes
1
answer
81
views
How can I find a Stable Diffusion program?
Well, I know that I'm going to ask too much.
So, I really want to ask you a totally (powerful (!)) free completely off-line code to generate prompt-based images like midjourney. I want to run with my ...
- 141
0
votes
0
answers
50
views
Context free grammar of $ L=\{a^nb^m, n\neq 2m\} $ [duplicate]
I have to find the context-free grammar of this language:
$ L=\{a^nb^m, n\neq 2m\} $
So I did:
$ S \to a \mid aYb \mid \epsilon$
$Y \to aSb \mid X \mid \epsilon$
$X \to bX \mid \epsilon $
is it ...
- 1
-1
votes
1
answer
82
views
Equivalence between Lambda Calculus [Church] and Computable Partial Functions [Godel]
In order to show that Lambda calculus and Turing machines are equivalent it is sufficient to show that you can simulate one in the other [both ways].
We can observe it in action. Can one do the same ...
- 141
1
vote
0
answers
32
views
"Reasonable" requirements for a computation model to be equivalent in power to a Turing machine
I was reading through Sipser's "Introduction to the Theory of Computation" and in it, he states that all computational models with unrestricted access to unlimited memory are "...
- 11
-1
votes
1
answer
94
views
Turing machine with infinite states
I want to ask about a turing-machine-like construct with an infinite number of states.
in this post the claim is that every language is accepted:
Can a Turing machine have infinite states?
I ...
- 1
1
vote
0
answers
53
views
Regarding constant * opt approximation in agnostic learning
In standard agnostic learning, we assume that there is a concept class $H\subseteq \{h:\{0,1\}^n\rightarrow \{0,1\}\}$. Given samples from a distribution $D:\{0,1\}^n\times \{0,1\}\rightarrow [0,1]$, ...
- 11
2
votes
0
answers
59
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 ...
0
votes
1
answer
56
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
46
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
106
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 ...
1
vote
1
answer
62
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
395
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
33
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
69
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
66
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 ...
- 141
25
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 ...
- 380
2
votes
1
answer
66
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 ...
- 358
2
votes
2
answers
283
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'...
- 512
1
vote
0
answers
24
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 ...
- 11
2
votes
1
answer
68
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 ...
- 123
2
votes
0
answers
37
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)\...
- 21
2
votes
1
answer
101
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 ...
- 21
1
vote
1
answer
397
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 ...
- 261
0
votes
1
answer
242
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-...
- 453
0
votes
1
answer
34
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 ...
- 45
2
votes
2
answers
151
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 ...
- 305