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.

367 questions
403 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 ...
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 @...
2k 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 ...
132 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}...
53 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 ...
226 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 ...
173 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 ...
737 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....
318 views

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 ...
175 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 ...
2k 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 ...
49 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 ...
72 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 ...
55 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 ...
81 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 ...
59 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 ...
29 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://...
81 views

Turing Completeness of System Which Randomly Fails to Complete Calculations

If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python ...
100 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 ...
95 views

ORAM: Is it generic?

Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independent of ...
177 views

CFG Equivalent of regular expressions

So I was wondering something about the Chomsky hierarchy. DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages. Right-regular or left-regular grammars produce regular ...
314 views

Context-free and context-sensitive grammars in FSM with counters

Consider an extension of finite-state machines that utilizes a finite set $C$ of counters. Let's call them counter automata. Before execution, each counter $c\in C$ is set to zero. Every transition, ...
294 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 ...
403 views

How do nondeterministic Turing machines compute general function problems?

(Hope this hasn't been asked before, but I didn't find anything.) In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. ...
70 views

runtime of problems vs algorithms

I know that a solving a specific problem can have different runtimes on different models of computation. But can a specific algorithm have different runtimes on different models of computation? Also, ...
32 views

Is there a broader class of total functions than $PR$? [duplicate]

In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann ...
46 views

Primitive Recursion equipped with an evaluator function

The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ev(i,j)$ which computes the $i$th primitive recursive function on ...
65 views

Theoretical justification of “halting problem avoidance”

The wikipedia page for the Halting problem mentioned practical solutions to avoiding the halting problem such as avoiding infinite loops. And there is a mention that "by restricting the capabilities ...