Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

7
votes
1answer
203 views

Reversible Turing tarpits?

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might ...
13
votes
2answers
344 views

Provable gaps between decision tree complexity and “true” complexity

The title is a little misleading: but hopefully the question isn't: Grønlund and Pettie's new result showing that 3SUM has only $O(n^{3/2})$ decision tree complexity got me wondering: Is there a ...
0
votes
0answers
59 views

Machine models based on group-labeled digraphs?

Following an earlier question, I would like to suggest the following generic computation model. Let $\Gamma$ be a group, we say that a $\Gamma$-labeled digraph is a digraph $G$ whose arcs are labeled ...
2
votes
2answers
168 views

Difference between abstract machines and calculi

So, first of all: I'm not sure how to tag this question. Feel free to tag it differently. I recently started reading up on CHAMs, which can express different process calculi. Slightly confused, I go ...
5
votes
2answers
165 views

Why do we need PAP (partial aplication) objects in heap?

In the paper “Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages” by Simon Marlow and Simon Peyton Jones it is told that a PAP heap object may be created in the push/enter model ...
1
vote
3answers
432 views

Does mathematical model for conccurent computations exist?

Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time? If yes, how are the concurrent computations ...
8
votes
0answers
104 views

Cell probe model vs transdichotomous ram

can someone explain me the difference between those two (cell probe model and transdichotomous ram)? In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of ...
5
votes
6answers
566 views

Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics?

This guy asserts: I’ll say it — the computer was invented in order to help to clarify … a philosophical question about the foundations of mathematics. (This problem being Entscheidungsproblem - ...
12
votes
3answers
600 views

Can any program be implemented mechanically?

Is it possible to build a single purpose (non Turing complete) mechanical implementation of say, Microsoft Word? Is it possible to implement such things as iterators, first-order functions, the whole ...
-3
votes
1answer
328 views

Minimal Turing Machine implementation / Von Neumann UC [closed]

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
24
votes
6answers
4k views

Applicability of Church-Turing thesis to interactive models of computation

Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. ...
11
votes
1answer
719 views

Feasibility of Gödel machines

Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine It's a general problem solver which is capable of self-optimization. It's suitable for reactive ...
2
votes
2answers
214 views

Difference between Stencil -structures and Cellular Automata Category-theoretically?

Definitions Stencil = "For a given point, a stencil is a pre-determined set of nearest neighbors (possibly including itself)." (source) Wikipedia's definition (source) = It ...
6
votes
2answers
310 views

Which model of computation to simulate to prove universality?

I am starting out in theoretical computer science. I have a model of computation based on observations of auto-associative memory in the brain. I believe (with little evidence) that I can do ...
21
votes
0answers
256 views

Adiabatic quantum computing with level crossings

Question. In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is ...
2
votes
4answers
509 views

Examples of reversible computations

Irreversible computations can be intuitive. For example, it is easy to understand roles of AND, OR, NOT gates and design a system without any intermediate, compilable layer. The gates can be directly ...
1
vote
0answers
160 views

What is the the optimal computational model for memristive style CMOS?

I'm a bit new to the practical use of memristors in general, but I'm starting to see it as a (3D stacked) grid of components that could be treated as transistors or flip-flops on demand (which may be ...
3
votes
1answer
148 views

Prefix Dictionary Problem in External Memory

I'm interested in an external memory data structure able to support the following operations on variable length binary sequences: (1) Insert such a sequence. (2) Given a query sequence, find the ...
11
votes
3answers
388 views

Is the MapReduce framework a type of BSP?

Is it accurate to call the mapReduce framework a type of bulk synchronous parallel programming framework with no local memory retention within processors between synchronizations? If not, what ...
18
votes
3answers
517 views

What is the right theoretical model to design algorithms for current and upcoming high performance computers

This question is similar to a more general question for what is the right theoretical model of a computer to design algorithm and data structures in. Here, I ask specifically about current high ...
8
votes
5answers
464 views

Natural computation based on fundamental forces

Well-known examples of computation inspired by natural phenomenon are quantum computers and DNA computers. What is known about the potential and/or limitations of computing with Maxwell's laws or ...
2
votes
1answer
389 views

Assistance in showing computational equivalence between software and hardware computing systems

I'm in the middle of a discussion regarding the equivalence of software and hardware computing systems, and I would like some comment. Any arguments and/or documentation (supporting or dissenting) ...
13
votes
6answers
397 views

What is known about the effectiveness of reliable computing?

How well has the following problem been investigated in TCS? (I apologize if the problem statement sounds vague!) Given a Model of Computation MC (Turing Machine, Cellular Automata, ...
16
votes
2answers
2k views

Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp. The algorithm is universally reported to run in $O(2^n n^2)$ time. ...
6
votes
0answers
266 views

Are there any models of computation currently being studied with the possibility of being more powerful than Turing Machines? [duplicate]

Possible Duplicate: What would it mean to disprove Church-Turing thesis? Are there any models of computation currently being studied with the possibility of being more powerful than Turing ...
13
votes
0answers
884 views

Can a Penrose tile cellular automaton be Turing-complete?

This question was based on an incorrect premise ... see Colin's comment below. Forget it. This was inspired by the discussion on this Math Overflow question. First, I need to define our terms. In a ...
30
votes
5answers
1k views

Which model of computation is “the best”?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
1
vote
1answer
213 views

Decide if number is negative (in URM machine like language)

So I'm learning to program in an assembly language for an abstract machine wich is very similar to an URM Machine. An URM machine has 3 basic instructions (or 4 in some literature): To zero a ...
11
votes
1answer
371 views

Do people look at loop nestness in boolean circuits?

While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought ...