Skip to main content

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
2 answers
874 views

Do analog computers exist?

Given the current state of physics and quantum mechanics is it possible theoretically to build an analog computer that, for example, calculates the addition of two real numbers? Where theoretically if ...
JobHunter69's user avatar
0 votes
1 answer
122 views

Analog computers more powerful than turing machines?

Ignoring quantum mechanics for a moment, is it true that analog computers are more powerful than turing machines? for example an analog computer can add two irrational numbers together, but a turing ...
JobHunter69's user avatar
0 votes
0 answers
17 views

Basic illustration of universal computation in Margenstern's work on Cellular Automata in Hyperbolic Spaces

I am fascinated with these two hyperbolic tessellations, what Maurice Margenstern calls the heptagrid and the pentagrid. I have the two volumes/books he authored, but they are a bit dense for my not-...
Lance's user avatar
  • 2,243
0 votes
1 answer
51 views

Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?

I've been researching formal models for computing with real numbers and came across the field of computable analysis built on top of specifically the type 2 Turing machine, which allows for ...
KylerAce's user avatar
9 votes
14 answers
8k views

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

According to the Bekenstein bound, Turing machines are not realizable in real life. So why are they accepted as the standard for effective computation? You may as well consider more powerful machines ...
JobHunter69's user avatar
0 votes
0 answers
37 views

Why are languages fed as input into machines/automata as a stream and why do automata read one symbol at a time?

Consider an FSM augmented with a camera. The input is a book. First, the book is already stored without the FSM needing to have states to memorize the input. (The memory used to record the input is no ...
JobHunter69's user avatar
2 votes
0 answers
20 views

Is it decidable whether a Turing machine is universal? [duplicate]

I imagine the answer was negative, but I cannot find a proof of it.
Clément Dato's user avatar
0 votes
1 answer
22 views

Are there any example of practical application of counter machines?

I am currently working on a presentation over how counter machines are as effective as Turing machines. During my research, I found out that random access machines are an improved version of counter ...
Nerincet Vonwthaud's user avatar
0 votes
0 answers
23 views

Can one prove locality principle for emulation of Abstract State Machine?

Suppose we emulate some ASM in memory machine, like RAM machine or Turing machine. One ASM postulates is Bounded Exploration Postulate, which seems related. Can one prove some form of locality ...
uhbif19's user avatar
  • 101
3 votes
1 answer
65 views

Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?

There is a famous equivalence between types of grammars and automatons. However when discussing recursive functions, we only consider equivalence of General Recursive functions with Turing machines. ...
math boy's user avatar
  • 359
1 vote
1 answer
91 views

Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}

So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10 I created a DFA that could satisfy this requirement,...
cool cat's user avatar
-3 votes
2 answers
46 views

A more concise Finite Automata for 10 substring?

I am learning about finite automata and trying to create a machine that matches {w ∈ Σ∗| w does not contain the substring 10} I created a DFA where it either starts ...
user168855's user avatar
0 votes
1 answer
49 views

Lambda Calculus vs Turing Machine

How functional programming using lambda calculus is analogous to construction of Turing machine as per computational aspects?
soham singh's user avatar
0 votes
1 answer
16 views

Hardwiring input in DFAs and PDAs

A Turing Machine can be converted into a Turing Machine that has a specific input coded into it's description. This Turing Machine can then be run on empty input. Can we do the same for PDAs or DFAs? ...
Zee's user avatar
  • 243
0 votes
0 answers
36 views

Reading and answering a text question from a image?

I wanted to see what models would be best suited for providing a image (see the link below) and having the model perform a image to text (OCR of some kind) and laying out the contents of the image in ...
Pie's user avatar
  • 101
0 votes
0 answers
66 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 ...
Connor's user avatar
  • 101
0 votes
1 answer
40 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 ...
KGM's user avatar
  • 103
0 votes
0 answers
22 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/...
uhbif19's user avatar
  • 101
1 vote
1 answer
47 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 ...
Yannik Eik's user avatar
1 vote
0 answers
59 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}...
fiktor's user avatar
  • 111
0 votes
1 answer
39 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 ...
Nikita Artemenko's user avatar
-6 votes
1 answer
74 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 ...
Aland Ameer's user avatar
0 votes
0 answers
15 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 �...
Noah Carter's user avatar
0 votes
2 answers
125 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 ...
NotaChoice's user avatar
1 vote
0 answers
87 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/...
Noam Hudson's user avatar
0 votes
1 answer
95 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 ...
revision's user avatar
0 votes
0 answers
35 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 ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
228 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 ...
revision's user avatar
1 vote
1 answer
77 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 ...
Dannyu NDos's user avatar
1 vote
0 answers
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 &...
Corbin's user avatar
  • 230
-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?...
george's user avatar
  • 1
1 vote
1 answer
252 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 ...
Vladislav Ihost's user avatar
0 votes
1 answer
57 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 ...
Sbavert's user avatar
  • 51
0 votes
0 answers
150 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 ...
emdhdr's user avatar
  • 1
1 vote
0 answers
58 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 ...
Shadow43375's user avatar
1 vote
0 answers
83 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-...
Lance's user avatar
  • 2,243
0 votes
1 answer
293 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 ...
Pratik Hadawale's user avatar
0 votes
2 answers
104 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 ...
Trev's user avatar
  • 296
0 votes
1 answer
128 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 ...
harlydvi's user avatar
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 ...
domotorp's user avatar
  • 265
0 votes
1 answer
48 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 ...
P. Trinli's user avatar
  • 101
0 votes
1 answer
87 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 ...
M.N.Raia's user avatar
  • 141
0 votes
0 answers
73 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 ...
Mah's user avatar
  • 1
-1 votes
1 answer
91 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 ...
RFV's user avatar
  • 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 "...
Felix Zhang's user avatar
-1 votes
1 answer
174 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 ...
yaniv's user avatar
  • 1
1 vote
0 answers
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]$, ...
postasguest's user avatar
2 votes
0 answers
70 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 ...
Maksim Sidorov's user avatar
0 votes
1 answer
122 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 (...
Jahid Chowdhury Choton's user avatar
2 votes
0 answers
51 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 ...
Hans-Peter Stricker's user avatar

1
2 3 4 5
11