Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
3answers
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 ...
11
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 @...
6
votes
2answers
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 ...
0
votes
1answer
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}...
0
votes
2answers
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 ...
4
votes
4answers
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 ...
3
votes
1answer
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 ...
4
votes
1answer
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....
2
votes
0answers
318 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
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 ...
12
votes
3answers
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 ...
2
votes
0answers
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 ...
5
votes
1answer
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 ...
1
vote
3answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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://...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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, ...
1
vote
1answer
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 ...
8
votes
2answers
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. ...
1
vote
1answer
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, ...
0
votes
0answers
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 ...
6
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
195 views

Is the system of measuring length in the US Turing complete?

The author here writes: Little known fact, the system of measuring length in the US is Turing complete My question is: Is the system of measuring length in the US Turing complete?
2
votes
1answer
252 views

Turing Machine with additional finite memory of size $n$

The question itself: Let us define a generalization of Turing Machines to include a finite memory of >size $n$. We denote such a Turing Machine formally as: $M_{mem} = (Q, Σ, γ, δ_{mem}...
1
vote
0answers
100 views

Generate a graph to exact size using Kronecker product graph model

In network science, we can take sample a complex system and derive from this sampling a representative network (or graph) that describes the system to some extent. A model of a network, is a powerful ...
2
votes
1answer
50 views

Is there any count-preserving cellular automata which tends do “10101010…”?

Suppose that I have a bit string of finite length. Is there any bit rewriting rule rewrire :: (Bit,Bit,Bit) -> (Bit,Bit,Bit), that doesn't change the total count ...
1
vote
0answers
124 views

Construct DFA given oracle access to the language

I was given the following question. Given a minimal DFA $A$ with $m$ states over some alphabet $\Sigma$ which is a "black box" (you can only run words to it and it tells you if it accepts or not): ...
-1
votes
1answer
236 views

How can a Turing machine accept infinite number of inputs? [closed]

How it is possible for a turing machine to process an infinitely long input ?
2
votes
0answers
45 views

A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
3
votes
2answers
149 views

Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- ...
1
vote
2answers
98 views

PRAM with no bit operations and P vs NC

I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition anywhere....
73
votes
2answers
7k views

What does the “Lambda” in “Lambda calculus” stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the term?...
3
votes
0answers
81 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel ...
5
votes
2answers
175 views

What theorem are these? (from Scott Aaronson's blog)

Browsing Scott Anderson's blog, I found this list of theorem. Among them are: If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a ...
4
votes
2answers
692 views

Can one consider living (biological) cell to be Turing Complete?

Universal Turing Machine can be boiled down to two components. Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending ...
2
votes
1answer
145 views

Prove that the Kolmogorov complexity function cannot be approached from below

How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function? After some research it seems I must show the function $K(x)$ is not lower ...
3
votes
2answers
141 views

Why classification represents all computations?

I'm a computer science student taking a theory of computation class. Recently we were taught about what is computable and what is not and about the Turing machine. As I understood (please correct me ...
2
votes
1answer
286 views

Does a non deterministic Turing machine which is a decider halt on all branches for all inputs?

Does a non deterministic Turing machine which is a decider halt on all branches for all inputs?? I know it must halt on all branches for a string not in language, but for a string in language, NDTM ...
4
votes
1answer
65 views

Maximal class for which function equivalence is decidable

I previously asked if it's decidable whether two primitive recursive functions are equivalent: "primitive recursive functional equivalence". The answer was no. Here is my followup. What is the most ...
0
votes
1answer
75 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
44
votes
7answers
11k views

Is there anything that MUST be done on a multi-core CPU?

When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing ...
1
vote
0answers
32 views

About the SOS degree of a function and optimization algorithms for the function

Given a non-negative function on the hypercube $f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$ one says that it is of "SOS-degree" of $d$ (denoted as $deg_{SOS}(f) =d$) if $d$ is the minimum $k$ such ...
1
vote
2answers
271 views

Turing machine that can tell if it ends in standard position?

Suppose we have a TM $M$ with alphabet $\{0, 1 \}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape ...
2
votes
1answer
246 views

Why is universal turing machine considered with only one head?

While defining the following time hierarchy theorem (for deterministic case ) : If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$ The ...