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
3
votes
0answers
684 views

λ-Calculus extensions: meaning of extension symbols

When working with λ-Calculus I see lots of extensions that use other symbols such as ∀ <:Top {} ←, which are from "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce. ...
1
vote
2answers
35 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 ...
1
vote
1answer
48 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 ...
-1
votes
0answers
17 views

Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$

Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$. Hello, I have been trying to solve this problem, my intuition tells that ...
0
votes
0answers
15 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 ...
1
vote
1answer
47 views

Is there way to compare computing power used in two blockchains when every one of them is using different mathematical function as a Proof-of-Work?

If I am a Bitcoin node, I can evaluate two blockchains in terms of each one consisting of more Terahashes than the other and thus deduct which one is the "correct" one. There is impartial source of ...
0
votes
3answers
40 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 ...
0
votes
0answers
35 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?
5
votes
3answers
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 ...
1
vote
0answers
14 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? ...
2
votes
2answers
99 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 ...
4
votes
2answers
214 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 ...
3
votes
2answers
845 views

Can a petri net fire only one transition at a single moment?

After reading several articles about petri nets, I am confused on how firing works. Can Petri net system fire only one transition out of all active (fire-able transitions) at a single moment? Or are ...
2
votes
4answers
249 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
0answers
31 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 ...
1
vote
1answer
40 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 ...
12
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
2answers
42 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 ...
0
votes
0answers
12 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.
0
votes
2answers
647 views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
1
vote
1answer
21 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 ...
4
votes
0answers
90 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}$) ...
22
votes
3answers
543 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
2
votes
0answers
26 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 ...
5
votes
1answer
1k views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
1
vote
0answers
39 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 ...
7
votes
3answers
6k views

Why do pushdown automata use a stack?

I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?
8
votes
1answer
1k views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation. I was wondering whether combinational ...
0
votes
1answer
41 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
0answers
32 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 ...
1
vote
1answer
30 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
99 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 ...
0
votes
1answer
93 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}...
3
votes
1answer
51 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 ...
0
votes
0answers
24 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 ...
11
votes
4answers
1k views

Why is the tape not part of the definition of a Turing Machine?

I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, ...
-2
votes
1answer
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 ...
1
vote
1answer
38 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. ...
2
votes
2answers
99 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&...
6
votes
4answers
2k views

How is the computational power of a human brain comparing to a turing machine?

This seems related to these questions at a glance: What are some problems which are easily solved by human brain but which would take more time computers? What would show a human mind is/is not ...
1
vote
2answers
123 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
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 ...
1
vote
1answer
67 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
56 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 : &...
14
votes
9answers
12k views

Why does a Turing machine recognise exactly one language?

I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?
0
votes
0answers
53 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
83 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 ...

1
2 3 4 5
10