# Questions tagged [machine-models]

The tag has no usage guidance.

51 questions
Filter by
Sorted by
Tagged with
-3 votes
1 answer
98 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. ...
• 295
0 votes
1 answer
114 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....
7 votes
1 answer
143 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$, ...
• 5,531
3 votes
2 answers
151 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
• 186
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 ...
• 5,127
6 votes
2 answers
394 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 ...
• 775
1 vote
1 answer
114 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 "...
• 1,177
2 votes
0 answers
99 views

• 23.1k
7 votes
0 answers
377 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 ...
• 283
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 ...
• 24.3k
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 ...
2 votes
1 answer
355 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 ...