# 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.

453 questions
Filter by
Sorted by
Tagged with
59 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 ...
38 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 ...
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.
478 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 ...
15 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 ...
44 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 ...
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}$) ...
520 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 ...
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 ...
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 ...
1k views

42 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 ...
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 ...
981 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, ...
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 ...
33 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. ...
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&...
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 ...
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 ...
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. ...
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 ...
46 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 ...
43 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 : &...
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?
51 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 ...
78 views

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 ...
3k views

### Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions? Edit: I am new to ...
1k views

### Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
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 ...
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 ...