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
1
vote
4answers
789 views

Does a computer do only two things?

According to the book, Introduction to Computation And Programming Using Python by John V Guttag, a computer does only two things: Store data Manipulate data But is this all? I mean, without I/O, ...
2
votes
1answer
361 views

RAM Machine and FSM

I heard that it's possible to model a bounded-memory RAM as a Finite State Machine. I'm curious about the method of how we would do that. How would you model a bounded-memory RAM as a Finite State ...
2
votes
1answer
123 views

How to extent primitive recursion from natural numbers to finite strings?

Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification ...
4
votes
1answer
69 views

Computing with number of stack items

For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete? Is it enough to be able to access just the top-most item? Two ...
3
votes
3answers
705 views

Are partial recursive functions analogous to recursive languages or r.e. languages?

From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979: The assumption that the intuitive notion of "computable function" can be identified with the class ...
2
votes
2answers
4k views

Meaning of ε in NFA-ε?

In wikipedia NFA-ε transition function defined as follows $Δ : Q × (Σ ∪ \{ε\}) → P(Q)$, where $Σ$ is an alphabet and $ε$ - empty string. I don't understand the meaning of $ε$ in this context. ...
1
vote
1answer
90 views

Is there a known algorithm for computing the n-th Turing machine directly? [duplicate]

Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M_1$ can be represented by 9,900,599 ([0 0 halt],...
0
votes
1answer
260 views

How can a Turing machine write the description of the n-th Turing machine?

I am trying to interpret the following problem: "Describe an algorithm for a Turing machine which receives the integer n as input and proceeds to write the description of the n-th Turing machine from ...
7
votes
1answer
174 views

Does "not regular" imply "acceptor needs memory"?

Regular Languages, by definition, can be accepted by finite automata, which do not have memory. But if I know that a language is not regular, does that imply that any mechanism that recognizes the ...
1
vote
0answers
130 views

Addition Register Machine

In an abstract register machine, is it possible to add two registers together without losing one of the summands, but without using a third register? That is to have a register machine that maps $(m,...
3
votes
1answer
85 views

Do formulas involving fewer repetitions of variables give higher numerical precision?

I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis. Exercise 2.15. Eva Lu Ator, ...
1
vote
3answers
2k views

Why an ARM processor with 32 bits address bus can address 4 billion different bytes?

Why an ARM processor with 32 bits address bus can address 4 billion different bytes? I know that $2^{32}$ is equal to about 4 billions, but shouldn't it be 4 billion bits and not bytes? Hence if I ...
3
votes
1answer
72 views

Prove that $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable

I want to prove that: $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable. Here $w$ is a string and $B(n,w)$ is the set of all $n$-state ...
1
vote
0answers
163 views

Implementation of function [closed]

We have that MIMA (Neumann MInimal MAchine) has the following commands: I want to implement the Mima-command EQL adr (equal?) with the other Mima-commands. We have that for that command it ...
1
vote
2answers
396 views

Variant of Turing machine

How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the ...
5
votes
0answers
171 views

Is $E_{LBA}$ a Turing-recognizable language? [closed]

I know that $E_{LBA} = \{\langle M \rangle ~ \mid ~ L(M) = \emptyset \}$ is an undecidable language, but is it recognizable (recursively enumerable)? It seems that it's complement is recognizable ...
34
votes
5answers
47k views

Difference between a turing machine and a finite state machine?

I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one ...
4
votes
1answer
164 views

Using analog values with Algebraic Normal Form?

Algebraic normal form (ANF) is a way of describing digital circuits made up of AND and XOR gates. The below is an example of an ANF expression which evaluates to true if two or more of it's three ...
2
votes
1answer
81 views

How does universal calculator work?

As I understand, the concept 'computation' started dependent on hardware (like looms for instance). The Hardware defines (physical cascades) what happens between input and output. I think I saw in ...
-1
votes
1answer
265 views

In automata theory, why is a machine classified based on the languages it recognises?

Automata Theory is a subject where we mathematically model a computing device and study the theory behind it. Here we group the computing devices based on the number of languages they can accept. ...
9
votes
4answers
2k views

Theory of computation introductory curriculum

I want to study theory of computation on my own, so I am looking for books. What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation? ...
8
votes
5answers
607 views

Why are progress bars so inaccurate? [closed]

Computers and programming languages tend to be deterministic and predictable. Yet progress bars seem the opposite, especially if the operation is complex. Even for world class professional products, ...
0
votes
1answer
50 views

Characterisation of Turing completeness? [duplicate]

I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language. For example, an imperative language is Turing complete if it has ...
1
vote
1answer
220 views

Relation between Machine code and Von Neumann architecture

Since machine language executes instructions on ALU, CPU register and memory, is correct say that machine code abstract the Von Neumann model? If exists, semantically, what is the relation between ...
2
votes
1answer
373 views

Is Functional Complete means Turing Complete?

I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates. A Turing machine may halt or not in a particular ...
1
vote
1answer
167 views

Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine?

It is known that a Turing machine cannot predict the outcome of another Turing machine. Given a machine $M$ less powerful than any Turing machine (i.e. able to decide less languages, i.e. a subset of ...
2
votes
3answers
892 views

Why does computer have branch and jump instructions

I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist. I am asking what theory ...
1
vote
1answer
594 views

Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially? [duplicate]

I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be ...
1
vote
1answer
349 views

Two-head one way finite memory machine accepts non-regular languages

I'm having trouble proving, or understanding why a two-head one-way finite memory machine could accept a non-regular language– for instance, $(w \mid w \in (a,b)^{*}, w= a^i b^i, i\geq 0)$. For ...
1
vote
1answer
108 views

What problems are solvable in Datalog?

Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what ...
0
votes
2answers
167 views

Can other models of computation equivalent to Turing machines also recognize the same languages?

There are other models of computation equivalent to Turing machines in terms of computability. Turing machines also recognize recursively enumerable languages. My questions are Do other models of ...
10
votes
1answer
1k views

Algorithm Complexity Analysis on functional programming language implementations

I've learned today that algorithm analysis differs based on computational model. It is something I've never thought about or heard of. An example given to me, that illustrated it further, by User @...
3
votes
2answers
100 views

Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question: "This question is about recursion. A recursive method can always be implemented by an iterative method ...
6
votes
2answers
4k views

Is there a way to test "Turing completeness"?

I asked my algorithms teacher today the very same question that is stated in the title, but he seemed a bit unsure, either on the question or on the concept, so I thought I'd try here too. Is there a ...
0
votes
3answers
147 views

Computing composite functions

This may not be strictly a computer science question but is related. Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is ...
0
votes
1answer
146 views

Show this function is partially computable

Let B(x) be a computable predicate. Show that \begin{equation} G_B(r)= \begin{cases} 1 \;\;\;\;\;\text{ if there are at least r numbers n such that B(k) = 1 } \\ \uparrow \;\;\;\;\; \text{ otherwise}...
0
votes
2answers
68 views

Is a physical process with unbounded input Turing equivalent?

Church-Turing thesis states that any effectively computable process is computable by a TM. Let's assume for now that it means that every physical machine is computable by a TM. Let's call it A. Now ...
4
votes
4answers
281 views

Is computation independent of hardware?

We use electronics to build computers and do computation. Is computation independent of the hardware we use? Would it be possible to do whatever a computer does with pen and paper? If computation is ...
3
votes
1answer
448 views

Does the amount of symbols a turing machine has affect what computations it can perform?

Do additonal symbols on a turing machine actually change what is computationally possible on a machine, or do they just make them easier to work with? For example is there anything a 3 symbol turing ...
5
votes
1answer
1k views

Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?

I've just started reading about theory of distributed systems and am a bit confused. There seem to be two ways of defining a synchronous distributed system and I'm not sure whether they are equivalent....
3
votes
1answer
294 views

Smallest set of features that would make relational algebra Turing complete

I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete. Probably just recursion (something like "MY_QUERY(param) = select * from param UNION ...
2
votes
0answers
378 views

Explaining TM notation in Lewis/Papadimitriou

I was working on some questions in the book "Elements Of The Theory Of Computation", by Lewis and Papadimitriou, and I need help with one question - question 4.1.8 (chapter 4): Give the full ...
2
votes
2answers
325 views

Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?

When a CPU simulates a certain program, as they do all the time, this is inherently slower than if the program would have been "baked in" into the hardware and computed directly. We know this from ...
2
votes
0answers
55 views

Typed representation of a memory model

Assume a simple procedural language, where statements write and read from local memory via references and procedures accept arguments of n different scalar types (say floats, ints and strings) and ...
5
votes
1answer
88 views

Sequential execution in $\pi$-calculus

I am relatively new to $\pi$-Caculus and have a doubt wrt sequential execution in In $\pi$-Calculus . Does passing of common names over common channels shared between two Agents, represent a ...
1
vote
3answers
80 views

Count elements in the real world in constant time by weighing them

I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out ...
1
vote
1answer
92 views

Can a simulation be conducted in which the inhabitants would observe infinite time divisibility?

In this video, a physics theorist talks with his collegues claiming to have found evidence for Simulation Theory. I'm not here to ask about the various proofs for and against ST - that's basically in ...
0
votes
0answers
75 views

Keywords for the science articles search (parallel computing)

Often, similar ideas or works have vastly different namings or covers. This is a hassle for searching in distant fields, especially in a non-native language. Idea. We mathematically model (Petri ...
0
votes
0answers
32 views

Why does not the result in this notes show P is not NP in BSS model?

As far as I know (not understand that well though) BSS model is a real computation model and $P_{\Bbb R}\neq NP_{\Bbb R}$ is a real analog of $P\neq NP$ problem in BSS model. The lecture notes http://...
3
votes
1answer
169 views

A modified version of two way DFA

Following an exercise from Hopcroft-Ullman's Introduction to automata theory: Let's define $k-MDFA$ as two way deterministic finite automaton with $k$ markers, similarly to two way $DFA$ but with ...

1
4 5
6
7 8
10