# 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
Filter by
Sorted by
Tagged with
1 vote
47 views

1 vote
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/...
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 ...
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 ...
1 vote
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 ...
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 ...
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 vote
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 &...
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
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 ...
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 ...
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 vote
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 ...
1 vote
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 "...
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 vote
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]$, ...
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 ...
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 (...
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 ...
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