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
0 answers
27 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)\...
user avatar
  • 21
2 votes
1 answer
62 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 ...
user avatar
1 vote
1 answer
56 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 ...
user avatar
0 votes
0 answers
18 views

Where are some examples of unsatisfiable formulas? Especially about 3CNF paradigm

I've been learning co-NP recently. I know that UNSAT $\in$ co-NP. So I want to find more examples of UNSAT, especially about 3CNF paradigm.
user avatar
  • 141
0 votes
1 answer
30 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-...
user avatar
0 votes
1 answer
26 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 ...
user avatar
2 votes
2 answers
88 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 ...
user avatar
2 votes
1 answer
51 views

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$ Here is what I have tried: 1. Starting State Read $a$, Write $x$, Move Right, Go To 2 Read $x$, Write $x$, Move Right, Go To 1 Read <...
user avatar
  • 121
0 votes
0 answers
19 views

What is the computational class of neural networks?

What is the relationship between formal automata and the different types of neural networks? What kind of neural network would you need to be able to parse context-sensitive languages, for instance?
user avatar
1 vote
1 answer
51 views

A decidable language that can't be decided by a circuit ensemble of linear size

Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
user avatar
0 votes
1 answer
24 views

Why are reachability trees meaningful for Petri Nets

To construct a reachability tree we start with the initial marking and then consider all enabled transitions and fire them one by one. That is, we find the marking corresponding to firing each. I can'...
user avatar
  • 123
4 votes
2 answers
103 views

Do all Turing-complete programming languages have to contain infinite loops?

Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below: Conjecture. There does not exist a set $...
user avatar
2 votes
0 answers
48 views

Differences between a computation model and an abstract data type

I am wondering about the difference between an abstract data type (ADT) and a computation model. As I understand them: A computation model defines the basic unit of computation, that is, what can be ...
user avatar
  • 121
1 vote
0 answers
52 views

Confused about the concept of deciding in nondeterministic Turing machines

I read this discussion before. However i’m still confused. I used to think a language decided by a NTM if for every input $w$ in $\Sigma^*$, all of the branches in computation tree leads to a halting ...
user avatar
0 votes
0 answers
35 views

In search for a complete definition for write-only TMs / Tapes

In the following lines I will present my question, whose content is divided in two parts: Preparation and Actual . (1) — Preparation Regarding the formal definition of the (one tape) general Turing ...
user avatar
0 votes
0 answers
25 views

Why do we promote Ubiquitous Computing when there are problems out there that cannot be solved computationally?

According to Alan Turing, there are 2 types of problems i.e. NP Complete and non-NP Complete, then why do we promote Ubiquitous Computing and introducing sensors and embedded systems into our daily ...
user avatar
  • 299
2 votes
1 answer
41 views

Is there a non PSPACE language s.t exponential padding of it is PSPACE?

I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that: Is there a language $ L \notin PSPACE $ over the alphabet {0,1} ...
user avatar
  • 21
1 vote
2 answers
51 views

Does multiplying word size numbers take constant time?

Does multiplying word size numbers (using standard grade school algorithm) take constant time? Can you use this to speed up computation and do the fast multiplication algorithms use this? By constant ...
user avatar
  • 83
1 vote
1 answer
52 views

Efficient comparison, using only sum, product, difference, and conditional jump if zero

I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
user avatar
0 votes
0 answers
20 views

Is a computational model that can instantly access any storage address and can access any arbitrary number of them at once more powerful then a TM?

This would be a computational model that would have unbounded space. But with a jump command that can access and do operations on any finite number of cells at once. Actual calculations would take ...
user avatar
0 votes
0 answers
68 views

Why EQ(cfg) is undecidable language?

I was studying Theory of Computation and I learned that EQ(cfg)[where the input is G1 and G2 both are CFGs and L(G1) = L(G2)] is undecidable but didn't understand why? Can you please explain it to me?
user avatar
5 votes
3 answers
3k views

How Turing Machine Can Never Stop?

My professor discussed the following Turing machine M' on input (,x): Generate number n Run M on X, for n steps If M stops, accept I don't understand No.3 If we are running M on input X for final ...
user avatar
  • 51
1 vote
0 answers
32 views

CEK machine vs SECD machine

What are the differences between the CEK machine and the modern variant of the SECD machine (which combines stack and dump) from the point of view of performance, memory efficiency, and other factors? ...
user avatar
  • 386
0 votes
3 answers
44 views

For 3CNF unsatisfiable boolean formulas, does it take exponential time to transform them into disjunctive form?

From the link Solving SAT by converting to disjunctive normal form, I learnt that the algorithm to transform any boolean formula to disjunctive form takes exponential time in worst case. But I have a ...
user avatar
  • 141
1 vote
0 answers
32 views

Lack of "Any" scan for Turing Machines

I was reading Charles Petzold's The Annotated Turing that walks through Turing's original proof out of curiosity and feel like I've missed something during the part where Turing is describing ...
user avatar
  • 11
1 vote
1 answer
44 views

Model of computation as "reverse engineered function"?

A model of computation is currently defined on wikipedia as: a model which describes how an output of a mathematical function is computed given an input. Is it therefore correct, at least as a rough ...
user avatar
  • 11
12 votes
8 answers
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 ...
user avatar
  • 254
2 votes
4 answers
257 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&...
user avatar
2 votes
2 answers
105 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 ...
user avatar
  • 3,464
0 votes
0 answers
13 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.
user avatar
1 vote
1 answer
35 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 ...
user avatar
-1 votes
2 answers
50 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 ...
user avatar
  • 254
4 votes
0 answers
92 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}$) ...
user avatar
2 votes
0 answers
31 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 ...
user avatar
1 vote
0 answers
41 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 ...
user avatar
  • 151
4 votes
2 answers
221 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 ...
user avatar
  • 115
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
36 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 ...
user avatar
0 votes
1 answer
44 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 ...
user avatar
  • 1,873
0 votes
1 answer
218 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 ...
user avatar
  • 3
1 vote
1 answer
32 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 ...
user avatar
  • 1,873
0 votes
1 answer
101 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}...
user avatar
  • 1
0 votes
0 answers
26 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 ...
user avatar
  • 1,873
3 votes
1 answer
98 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 ...
user avatar
  • 1,873
-2 votes
1 answer
60 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 ...
user avatar
1 vote
1 answer
42 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. ...
user avatar
  • 1,873
2 votes
2 answers
101 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&...
user avatar
  • 123
1 vote
2 answers
130 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 ...
user avatar
  • 111
0 votes
0 answers
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. ...
user avatar
2 votes
0 answers
41 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 ...
user avatar
  • 10.7k

1
2 3 4 5
10