# 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.

495 questions
Filter by
Sorted by
Tagged with
13 views

### How do you understand Systolic Arrays?

I'm working on a problem from the Digital Design and Computer Architecture course on Systolic arrays. The question set up is as follows: The following diagram is a systolic array that performs the ...
• 101
32 views

### Is it possible to compute the differentiation of any differentiable function on an interval?

It seems not because of the existence of irrational numbers in any interval, irrational numbers that have an infinite number of decimal digits that a computer is not able to manage?
34 views

### How are pointers modeled on bit-based computer models?

Why bit-based computer models? The perhaps most commonly used computer model is a random access machine that can store natural (or even real) numbers in infinitely many cells indexed by natural ...
• 103
20 views

### Are ASM and TLA+ somehow related?

I learned about abstract state macines recently, and on first sight they seem somehow reminiscent to TLA formalism. For example both: Are used to research possible state sequence and prove safety/...
• 101
1 vote
41 views

### How to formally show computational equivalence or universality using encodings?

I want to formally show that a computational system $\mathcal M$ is computationally universal by showing it is computationally equivalent to some already known universal system, i.e. some UTM. To show ...
1 vote
55 views

1 vote
42 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/...
22 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
32 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
140 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
1 vote
51 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 ...
• 335
49 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
10 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
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 vote
168 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 ...
56 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
111 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 vote
55 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
54 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
216 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 ...
77 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
63 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 ...
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
45 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
83 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
59 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
84 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
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 "...
112 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 vote
54 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]$, ...
64 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 ...
69 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 (...
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 ...