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
11
votes
8answers
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 ...
0
votes
3answers
83 views

Can there be a computer without software (only hardware)?

Can there be a computer without software (only hardware) which can produce meaningful output? "Software" would be for example an operating system (whether in the level of "firmware&...
1
vote
1answer
61 views

Mathematical models of computation that capture more advanced OS and CPU design features

The universal Turing machine is the standard theoretical model of a stored-program computer. While in one sense as general as possible (Turing completeness), it doesn't explicitly contain many of the ...
0
votes
0answers
11 views

Need literature on First order logic definibility through Automata

Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
1
vote
1answer
16 views

How is it possible that for infinite L in R exists subset L' which is not in Re?

Proove that for every infinite $L \in R$ there is a $L' \subseteq L$ s.t $L' \notin RE$. How can I proove it? if sketched on venn diagram it doesn't make sense... From my point of view everything ...
0
votes
2answers
40 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 ...
4
votes
0answers
85 views

Necessity of encoding for certain models of computation

Consider the following model of computation (from here). Although Fractran is Turing-complete, it assumes that the "user" is able to perform the steps of encoding the input ($2^{n + 1}$) ...
2
votes
0answers
20 views

Reference/textbook on RAM model/model of computation for algorithms

Can someone recommend a reference/textbook on the RAM model of computation? Preferably something with a concise definition and doesn't get too much into computer architecture. I'm very fine with this ...
1
vote
0answers
38 views

Puzzled by this interview problem of scheduling a computation graph on a single-processor under a memory constraint

I recently went through a interview session for a SWE/CS role at a well known company. It wasn't specifically a "coding-round" but was titled a "domain interview" session, so I ...
4
votes
2answers
204 views

Why did finite-state controller with datapath win?

I just finished watching the 1986 SICP lectures, and the concepts are rolling around in my head. My question: why is "finite-state controller with datapath" the implementation of computer ...
0
votes
1answer
16 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 ...
0
votes
0answers
23 views

The role of diagonalization - asymmetry between TM and Recursion Theory

This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can. First, here is an hypothesis: diagonalization is syatematically used to prove ...
0
votes
1answer
37 views

What is the formal mathematical model of a register machine?

I have been searching the web for a mathematical model of a register machine and have fallen short. The closest I have found is found here: But I am looking for more detail than what is provided ...
0
votes
1answer
29 views

Why is $EQ_{cfg}$ not recognizable but is co-turing-recognizable

I've seen the proof that $EQ_{CFG}$ is not recognizable but its complement is, my problem is that in the proof that it's complement is recognizable, it says that we test every string in $\sum^*$ and ...
1
vote
1answer
27 views

What is a generalized automaton that has ability to look up anything in memory from environment?

An automaton determines its next state from the current state and the next input symbol. A pushdown automaton adds a stack which you can push/pop/read from. But then there are probably a lot of ...
0
votes
1answer
77 views

Counting strongly connected components in a directed graph in $NL$

Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$ I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
0
votes
0answers
22 views

How does the railway model of computation get translated to motion on the heptagrid tiling of the hyperbolic plane?

I have been reading these, along with slowly chipping away at the two books Margenstern has produced: A universal cellular automaton in the hyperbolic plane A Universal Cellular Automaton on the ...
2
votes
1answer
43 views

How are two registers are enough to simulate a Turing machine?

The paper A universal cellular automaton in the hyperbolic plane says: Our simulation consists in simulating the execution of a register machine. It is known that two registers are enough to simulate ...
-2
votes
1answer
57 views

Simplify $X'(X+Y) + (Y+X.X) ( X + Y') + Z + X.Z$

I wanna know if $X'(X+Y)$ means $X'.X+Y.X'$? Does it have an AND gate after $X'$? Notation: $X'$ : NOT $X$ $X + Y$: $X$ OR $Y$ (OR gate) $X.Y$ : $X$ AND $Y$ (AND gate) New to boolean, can't seem ...
1
vote
1answer
34 views

Is a register machine built out of automata of some sort?

I am looking at register machines like the Random Access Machine. Wikipedia says: Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. ...
1
vote
2answers
83 views

How do we define the term "computation" across models of computation?

How do we define the term computation / computable function generically across models of computation? Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function&...
1
vote
2answers
102 views

Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model

For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have ...
0
votes
0answers
22 views

How to find the relation between two models, and sort of inductive bias is that is implemented in those models

I am pretty new with data science and Machine Learning. I am learning form one textbook and I found this task. I have no Idea from where to start and what relation could be. Any help would be great. ...
2
votes
0answers
40 views

A simple, concise, strong and a formal model of computation

Most mathematical objects can be said to be defined in simple terms, are usually really concise and still manage to capture the essence of what they are trying to talk about. For example, topology ...
1
vote
1answer
58 views

Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory?

Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the ...
1
vote
1answer
45 views

Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer

Well in many texts and places I have seen a called statement, which claims it self to the famous "Church Turing Thesis". I have seen many texts say that based on Church-Turing Thesis : &...
0
votes
0answers
52 views

Chomsky Hierarchy of a Computational Model

I am interested in knowing the Chomsky hierarchy of a particular computation model. Also, I would like to know if it is equivalent to Finite State Machine or is Turing complete. This computation ...
0
votes
1answer
78 views

Is the following language regular; context-free but not regular; or not context-free?

Let $\Sigma=\{0, 1, \#\}$. Is the following language regular; context-free but not regular; or not context-free? Justify your answer $$L=\{x\#y :\ x, y \in\{0, 1\}^∗\text{ and }\operatorname{bin}(x) + ...
1
vote
0answers
11 views

About the paper Privacy-preserving in association rule mining using an improved discrete binary artificial bee colony

I don't understand two parts in this paper: The min notion on page 4 line 357 (equation 10d): I understand this as to find all the $M_{10}$, $M_{11}$, $M_{01}$ first and then try to minimize the ...
0
votes
0answers
23 views

Do Field separators delimit only fields or also data units inside fields?

At least intuitively, I understand the following terms to be rigorously associated: Field Separator (FS) as a delimiter which delimits text segments such as words, sentences or lines/fields and an ...
1
vote
1answer
22 views

Explanation of roofline model

I am currently studying the roofline model. Wikipedia [2] shows the following example graph: The diagonal line shows $\beta * I$. But I do not understand why this line does not go through the zero ...
2
votes
1answer
87 views

Complexity of inverting a diagonal matrix

What is the complexity of inverting a $n \times n$ diagonal matrix? From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its ...
0
votes
0answers
37 views

Are there words without fixed size length?

Here, Yuval Filmus wrote: Unary encoding is only relevant in contexts where the length is not fixed. Are there words without fixed size length? Is there a Computer Science theory which describes ...
0
votes
1answer
81 views

EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we ...
0
votes
0answers
35 views

On the queue automaton and acceptance of this language

We have this language: $$ L = \{𝑥𝑥^r|𝑥∈Σ^∗\} $$ We want to show that it can be accepted by QA. consider a letter like #, before anything we push it to the queue. using this additional letter, we ...
0
votes
0answers
16 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 ...
1
vote
0answers
59 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
0answers
18 views

What the the most efficient and effective VM ISA/computational model format backed by research?

The JVM and CLR are stack based machine are very efficient, mainly due to the investment in these platforms than an efficiency and effectiveness of stack based VMs. For en entity that does not have ...
2
votes
0answers
28 views

Generalizing Quantum Computation

When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to ...
1
vote
1answer
41 views

What is the language of Sigma^n? Confused about meanining

I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet? Thank you so much!
2
votes
1answer
51 views

Programming languages and Model of computations

I am learning about model of computation and I found this wikipedia entry that categorises and outlines various model of computation. Now I want to know the programming languages that builds on these ...
0
votes
0answers
49 views

What is the difference between type theory and logic programming (in terms of declarative programming and specification)

How is does type theory (coq, lean, agda), and logic programming (prolog, datalog) differ from each other. Logic programming is a way of declarative specifying an algorithm, using classical 1st order ...
1
vote
0answers
17 views

Computational Model for learning Computability and Complexity

I was reading the book by Kozen-Theory of Computation. There is a statement that Turing machine is the best model for defining basic time and space complexity because atleast for higher levels of ...
0
votes
0answers
197 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
2
votes
0answers
58 views

Restrictions on Computational Methods (Art of Computer Programming)

In the Art of Computer Programming, Knuth describes a computational method as a quadruple $(Q, I, \Omega, f)$ where $I, \Omega \subseteq Q$, $\Omega$ is pointwise fixed, and each $x \in I$ defines a ...
0
votes
0answers
25 views

Power of Multi Tape and Multi Track Turing Machine

How can we prove that the computational power of Multi Track and Multi Tape Turing Machine is same as the Normal or Standard ( One Tape- One Track- One Head) Turing Machine?
0
votes
0answers
38 views

Context-Free Grammar Question

Given a regular Expression: 0^a 1^b 0^c, where a+b=c and a,b,c >= 0. Find the cfg for this expression. Here is what I tried to do: s -> AsB A -> 01 B -> 0 But then a language could be ...
0
votes
1answer
47 views

Black-Box Machine

Suppose we have mysterious machine which return median $m$ of given set $S$ and set $S/\{m\}$ in constant time, where $S/\{m\}$ denotes the difference of $S$ and element $m$. Prove that we can sort ...
4
votes
1answer
85 views

A language that is not context free

I working through some textbook exercises, and came across a problem that I'm struggling with. Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL. I've got the idea ...
1
vote
1answer
176 views

Empirical Risk and True Risk - Generalization Error Proof

I showed that, over an uncountable domain,learner A and a distribution P, such that for every sample size m and all samples S from $P^m$ $$ : L_S(A(S)) − L_P (A(S))| = 1 $$ Now I wanna prove for ...

1
2 3 4 5
10