# Tagged Questions

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.

24 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 ...
47 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 ...
38 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 ...
62 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 ...
32 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 ...
20 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://...
30 views

### Consequence of P=NP in BSS model

We know that in the Valiant model the result VP=VNP would imply NP is in P/poly. Do we know any consequences in case P=NP holds in BSS model?
54 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 ...
28 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 ...
41 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 ...
73 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 ...
39 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, ...
45 views

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

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 ...
84 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. ...
58 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, ...
28 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 ...
25 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 ...
40 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 ...
117 views

### Is the system of measuring length in the US is 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 is Turing complete?
79 views