Questions tagged [machine-models]
The machine-models tag has no usage guidance.
51
questions
-3
votes
1
answer
104
views
Can one do descriptive complexity theory using abstract state machines?
I learned about ASM recently and was interested how it could used for descriptive complexity theory.
Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. ...
- 315
0
votes
1
answer
126
views
Formal differences between emulation and simulation?
Recently this question came up, and I've been unable to find a concrete answer.
When I was reading this paper on CRDTs, I was a little perplexed by the notion of emulation here in theorems 3.1 and 3.2....
CommunityBot
- 1
13
votes
4
answers
834
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 ...
- 95
14
votes
3
answers
714
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 ...
- 186
7
votes
1
answer
144
views
Is the following restriction of cellular automata / tile assembly / CRN a known model?
Consider the following model: we work in the $d$-dimensional grid $\mathbb{N}^d$, and we have an alphabet $\Sigma$.
The initial cell $(0,\ldots,0)\in \mathbb{N}^d$ is marked with some letter $\Sigma$, ...
- 661
3
votes
2
answers
157
views
Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals [closed]
Looking for some lecture videos (introductory level) on logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals
- 1,606
14
votes
1
answer
1k
views
Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Background: I recently stumbled upon the ...
- 27.5k
11
votes
2
answers
421
views
Are there protein-based computational models?
Is there a framework/formalism that defines computational models based on proteins other than Adleman's DNA model or this work by Cherry and Qian?
Edit 2020 (related models/ideas based on DNA):
DNA ...
- 463
7
votes
2
answers
436
views
Most general setting for fine-grained exponential-time complexity classes?
Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine.
By the Hennie-Stearns theorem, the same functions are computable in ...
- 27.5k
6
votes
2
answers
404
views
On the complexity of a "list" datastructure in the RAM model
I am interested in the complexity of a data-structure equipped with the following operations (similar to a list):
insertion of an element at a given position within the list
deletion of an element at ...
- 51k
1
vote
1
answer
117
views
Running an algorithm for fixed amount of time on RAM model machine
Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "...
- 12.1k
2
votes
0
answers
99
views
How fast can we perform DFT on a Log-RAM computer?
The question is how fast we can perform an $n$ coefficient discrete Fourier transform on the log-RAM model of computation. If we assume that we can do arithmetic operations on registers of size $\log{...
- 2,100
2
votes
3
answers
499
views
what is a model of computation, mathematically? [closed]
Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...
- 301
3
votes
0
answers
624
views
Convention for RAM machine models
When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used?
My understanding is that most problems use unit-cost ...
7
votes
3
answers
628
views
Where does the modern canonical version of the Turing machine come from?
Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions:
The Turing machine I learned about was ...
- 141
41
votes
6
answers
3k
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 ...
CommunityBot
- 1
4
votes
1
answer
230
views
Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model
What are implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model?
In opposite direction what are implications ...
- 4,504
7
votes
1
answer
416
views
Examples of quasilinear vs. essentially linear time translatable models
The Hennie-Stearns theorem says that $k$-tape Turing machines with $k \ge 2$ are intertranslatable with loglinear blowup ($O(t \times \log{(t)}$).
This would define an equivalence class of models, ...
- 2,577
4
votes
2
answers
267
views
Characterisation of P in terms of register machines
It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown.
It is relatively straightforward to prove that indirect addressing ...
1
vote
1
answer
597
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) ...
40
votes
7
answers
7k
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. ...
CommunityBot
- 1
3
votes
0
answers
160
views
Is there research on "minimal" Turing-universal Markov algorithms?
The Markov algorithm is a simple model of computation. For other models of computation, such as Turing machines, cellular automata, tag systems, etc., there is research on the "minimal" instances of ...
CommunityBot
- 1
14
votes
1
answer
701
views
Complexity class associated with exhaustive search
What is the complexity class associated with exhaustive search algorithms? (if there is one)
Is it NP or PSPACE?
Are there restricted models of computation capturing the class of exhaustive search ...
- 4,041
28
votes
0
answers
538
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 ...
- 21.6k
7
votes
0
answers
149
views
What can you do with a moving knife besides cutting a cake?
In the fair cake-cutting, two different computational models are used:
A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies;
A continuous ...
- 2,222
6
votes
1
answer
150
views
What is the state of the art research in analysing algorithms on GPU architectures?
I have found many papers on sequential algorithms that have been implemented and tested on GPU architectures. Each of these papers usually as a result contains the amount of speedup that was achieved ...
CommunityBot
- 1
0
votes
0
answers
85
views
Understanding MA protocol as a variant of TM for small space setting
MA protocol is one of the most basic models of interactive proofs.
Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive ...
- 17.4k
1
vote
0
answers
88
views
Implication of lower bounds in Boolean circuit to other models of computation
Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$.
Then, how strong can we say about how hard $f$ is in other models? ...
- 1,130
14
votes
2
answers
647
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 ...
- 51
0
votes
0
answers
76
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 ...
CommunityBot
- 1
3
votes
2
answers
310
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 ...
- 4,806
7
votes
2
answers
382
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 ...
- 13.9k
11
votes
1
answer
469
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 ...
CommunityBot
- 1
1
vote
3
answers
819
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 ...
- 696
5
votes
2
answers
306
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 ...
- 121
9
votes
5
answers
558
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 ...
- 681
2
votes
2
answers
416
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 looks ...
CommunityBot
- 1
8
votes
0
answers
178
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 ...
- 81
6
votes
6
answers
2k
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 - ...
CommunityBot
- 1
-3
votes
1
answer
842
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 ...
CommunityBot
- 1
18
votes
1
answer
2k
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 ...
- 32.1k
14
votes
6
answers
521
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, Kolmogorov-...
CommunityBot
- 1
5
votes
4
answers
921
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 ...
CommunityBot
- 1
16
votes
2
answers
5k
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. ...
CommunityBot
- 1
1
vote
0
answers
178
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 ...
- 21.6k
3
votes
1
answer
199
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.2k
11
votes
3
answers
648
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 ...
- 19k
20
votes
3
answers
586
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 ...
CommunityBot
- 1
7
votes
0
answers
378
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 ...
CommunityBot
- 1
15
votes
0
answers
1k
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 ...
CommunityBot
- 1