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.
1
vote
1answer
13 views
Is modulus capable of universal computation?
I heard once that you could translate any digital circuit into a modulus operation, perhaps modulusing against different numbers?
It was a long while ago though and don't remember where I heard it.
...
0
votes
1answer
32 views
Are Cellular Automata always computers?
I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer.
In the introduction part:
Cellular automata can be ...
0
votes
1answer
166 views
In principle, what is the relation between Artifical Intelligence and Turing machine?
I am working on my cs project about AI & Turing machines, so i know that Artifical Intelligence is meant to implement different algorithms into the machine {the computer} to solve a problem or a ...
2
votes
7answers
56 views
Is infinitely fast computer fundamentally impossible even theoretically?
This may get slightly philosophical, but consider the following program:
...
7
votes
1answer
216 views
Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?
Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
4
votes
1answer
41 views
Generative power and classification of matrix grammars
[Edited] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy.
In here it is stated that:
A matrix ...
11
votes
3answers
176 views
What specifically makes quantum computers useful?
I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic.
That seems to be what people point to as being what makes quantum ...
3
votes
2answers
51 views
How Cellular Automata is related to Automata Theory?
I have read about Automata Theory where it is about the study of abstract machines and automata.
And i know that an abstract machine takes the input, process it and create the output, just like ...
3
votes
3answers
55 views
Computational problem - definition
How should I understand the definition of computational problem?
A computational problem is a mathematical object representing a
collection of questions that computers might be able to solve. ...
4
votes
0answers
10 views
Computational complexity of emulating (untyped) λ-calculus with a queue machine
I am looking for bounds - both lower and upper - on the time, spacial, and state/symbol (i.e. number of states and symbols required) complexity of simulating the (untyped) λ-calculus with a queue ...
2
votes
0answers
16 views
Complexity bounds for Turing equivalence [closed]
I am looking for bounds - both lower and upper - on the time and spacial complexity of simulating Turing-complete systems with each other. (I am aware that both time and space are ill-defined with ...
4
votes
2answers
110 views
How to prove universality in complex systems?
I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once. The ...
1
vote
1answer
87 views
Does solving mathematical equations with Cellular Automata structures means it is universal?
I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure.
The ...
0
votes
0answers
13 views
Total Turing Machine Grammar [duplicate]
We know that the Turing Machine corresponds to the 'Unrestricted' set of grammars.
To what set of grammars does the Total Turing Machine correspond?
0
votes
1answer
40 views
Quantum computer memory size
Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers).
Does it also hold for memory size? Are QC going to have ...
9
votes
3answers
1k views
Infinite calculations in finite time
This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to ...
5
votes
2answers
91 views
Are Elementary Cellular Automata structures considered to be fractals?
I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata.
But, what about the other rules from ...
7
votes
3answers
194 views
Why is the tape not part of the definition of a Turing Machine?
I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, ...
2
votes
1answer
42 views
Chomsky hierarchy type determined by language
I have some modified automata and the task is to give the type of Chomsky hierarchy to it.
All task is between type 3 and 0 noninclusive.
For regular languages there are lot of tools and I can check ...
13
votes
5answers
4k views
Why is a quantum computer not capable of solving more problems than a classical computer?
On the Wikipedia page for quantum algorithm I read that
[a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are ...
11
votes
5answers
3k views
Could the Halting Problem be “resolved” by escaping to a higher-level description of computation?
I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox.
So I got to wonder: ...
0
votes
1answer
67 views
Model paths by regular languages [closed]
I want use DFA to describe a sequence of movements in a 2D-space (language will be the path accepted by automaton in a particular case).
That is a typical modeling problem: how can I encode a ...
2
votes
1answer
43 views
Simplest Turing-complete ruleset for Markov algorithm
Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?
3
votes
2answers
89 views
Classical Computation without NOT
Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible ...
2
votes
1answer
34 views
Disprove that a function exists that counts the turing machines that halt on $\epsilon$
Let $L(M_k) = \{ \langle M \rangle | M \text{ halts on }\epsilon \} \cap \Sigma^k $
Disprove that $\exists f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$.
I am not sure where I ...
3
votes
2answers
98 views
Universal binary rewriting system
What is the simplest example of a rewriting system from binary strings to binary strings
$$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$
that can perform universal computation? Binary string ...
0
votes
0answers
19 views
Is there a good model of computation for real numbers? [duplicate]
/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms.
The integer numbers case
Many algorithms use integers and their ...
1
vote
0answers
30 views
Markov algorithm: pick rule first, then position, or the other way around?
A Markov algorithm is a string rewriting system (well, not a set of rules but a list of rules since they need to be ordered) with a strategy for applying rules that ensures determinism.
I think the ...
4
votes
3answers
70 views
Are deterministic and nondeterministic Cellular Automata equivalent?
It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs.
I ...
8
votes
1answer
148 views
Is the unsolvability of the N-Body Problem equivalent to the Halting Problem
There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, ...
7
votes
1answer
54 views
Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model
From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
2
votes
3answers
108 views
Is there a name for an inverted state machine?
I recently needed something like a state machine, but with a slightly different use case.
In general, I would say a state machine knows about a set of states, and different events. Depending on the ...
10
votes
0answers
74 views
Machines for context-free languages which gain no extra power from nondeterminism
When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.
For the ...
1
vote
2answers
40 views
Transitions triggered by sets of events
In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a ...
1
vote
1answer
72 views
Computer Programs and lambda terms without normal form
λ-calculus an ideal mathematical model in which to interpret programs. A program can be interpreted as a lambda term, and the term can have or not have a normal form. What role the terms without ...
2
votes
0answers
34 views
NPDA, guessing capability and stack as an exclusive resource
Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA).
We can view a nondeterministic transition as a guess; for example if $L = \{x x^R ...
1
vote
1answer
56 views
RAM Machine and FSM
I heard it's possible to model a bounded-memory RAM as a Finite State Machine.
I'm curious about the method of how we would that.
Does anyone have a clue ?
Thanks in advance
9
votes
8answers
3k views
Why does a Turing machine recognise exactly one language?
I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?
2
votes
2answers
152 views
How is the computational power of a human brain comparing to a turing machine?
This seems related to these questions at a glance:
What are some problems which are easily solved by human brain but which would take more time computers?
What would show a human mind is/is not ...
3
votes
3answers
111 views
Splicing squares on a Turing Machine finite tape
Trying to explain a problem, I thought of a variant of Turing
Machines. It is unlikely to be new, but I do not recall ever seing it
before, and I wonder whether it has been used or has a name. The ...
4
votes
1answer
71 views
Is a LBA with stack more powerful than a LBA without?
Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful.
A LBA with stack should not be Turing complete, ...
2
votes
1answer
54 views
SPIN / Promela Verification [closed]
I have this code here which performs the 'leader election' among a specified number of processes. In Promela, it is written as:
...
0
votes
0answers
16 views
Forward jump turing machine and r.e languages [duplicate]
I was going through some exercises I found online and I am really stuck at this problem:
Consider Turing Machines with the following restriction: they are only
allowed forward jumps, i.e. if ...
3
votes
5answers
664 views
Do we need recursion in programming language to solve any problem?
My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions?
Assuming we are allowed to use: ...
5
votes
2answers
272 views
Is a stack machine with a forward read iterator Turing complete?
It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful ...
1
vote
1answer
66 views
Feynman finite state machine
In his lectures on computer science, Feynman talks about finite state machines:
he present a simple delay finite state machine
Let me now give a specific example of an FSM that actually does
...
3
votes
2answers
103 views
Halting Problem and Turing Degree and Reduction? [closed]
This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question.
for $ A \subseteq \mathbb{N}$ we ...
4
votes
1answer
129 views
Primitive Recursion and course-of-values recursion - examples?
I ran into examples that I not trivially understand on course-of-values recursion,
In defining a function by primitive recursion, the value of the next
argument $f(n+1)$ depends only on the ...
4
votes
1answer
45 views
Pi Calculus: Restriction necessary for molecular (atomic) action?
In "A Calculus of Mobile Processes, Part 1" [1], Milner et al. give an example for transmitting a pair of values $(u,v)$ from the process $P$ to either $R$ or $Q$ (see page 13). All three processes ...
-2
votes
1answer
68 views
Are finitely many statements resp. variables sufficient to compute every function?
I prepare for local complexity contest and review some old Interview questions banks. I get stuck in one problem and no idea how we can solve it. please share your idea or help with this question:
...
