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.

learn more… | top users | synonyms (1)

5
votes
2answers
153 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, ...
1
vote
1answer
36 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 ...
11
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 ...
9
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
65 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 ...
1
vote
1answer
30 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
68 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 ...
1
vote
1answer
31 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 ...
2
votes
2answers
80 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 ...
0
votes
0answers
28 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 ...
3
votes
3answers
59 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 ...
7
votes
1answer
125 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, ...
6
votes
1answer
52 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 ...
1
vote
3answers
104 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 ...
9
votes
0answers
68 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 ...
0
votes
2answers
38 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 ...
1
vote
0answers
28 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 ...
0
votes
1answer
20 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
8
votes
8answers
2k 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?
1
vote
2answers
144 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
107 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
61 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
41 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
642 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
256 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
61 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
98 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
125 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 ...
3
votes
0answers
30 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: ...
2
votes
2answers
74 views

Are device drivers state machines?

I know that device drivers are attached to device controllers, which have their own registers and some local buffer storage. I'm wondering if I can think of device drivers as little state machines -- ...
6
votes
2answers
175 views

Is there a clear definition of “computable” for models of computation which are not turing complete?

This is a follow-up of another question here, and I hope it is not too philosophical. As Raphael pointed out in a comment on my previous question, I don't really get the definition of "computable", ...
0
votes
1answer
35 views

Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC?

In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size." I think that this may be missing a ...
5
votes
1answer
100 views

Decomposition of the set of computable functions into base functions

Say I have some computation model/programming language $M$ (e.g. Turing machine or equivalent), and let $C_M$ be the set of all partial or total functions $f : \mathbb{N} \to \mathbb{N}$ computable by ...
1
vote
1answer
48 views

Is a k counter automata a special kind of PDA?

I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special ...
3
votes
1answer
113 views

I/O in Theory of Computation

I posted a question "Arbitrary Programs that halt" some days ago and now i think my doubt is a lot more clear. I concluded that in any arbitrary program that halts, control flow operations, ...
5
votes
2answers
216 views

Can a quantum computer (theoretically) do things a classical computer (literally) can't?

I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer ...
5
votes
1answer
163 views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything i have learned recently in Theory of Computation. I was thinking whether combinational ...
0
votes
1answer
36 views

Memory Requirement for a Computable Problem

I was thinking whether it is true that every computational problem intrinsically has a minimum ammount of memory required for any algorithm that computes it. But then i was confused to what "memory ...
2
votes
1answer
51 views

Difference between BSP model and synchronous round model in distributed computing

I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens: every node can send a message to ...
6
votes
2answers
186 views

Are there things an analog computer can do that digital computing cannot do?

The crux of the difference between analog and digital computing is the number of bits of precision available, right? Now, I know that in the Turing machine, numbers can be stored with any degree of ...
1
vote
0answers
56 views

Models of Computation and What they can model [closed]

Some days ago i've discovered that in most of what we call "models of computation ", we can possibly model tasks other than computation itself . For instance, in lambda calculus we can model control ...
1
vote
0answers
26 views

What mathmatical model shall be used for describing P2P processes interaction?

I am creating a distributed service system. It runs in the cloud on heterogeneous hardware. I am using C# .NET for business logic and C++ for different physics\chemical calculations. Having three ...
5
votes
2answers
160 views

Analog computers and the Church-Turing thesis

I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine): One class of challenges to the strong Church–Turing ...
15
votes
6answers
4k views

Is there a physical analogy to the Turing Machine?

Recently in my CS class I've been introduced to the Turing Machine. After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine. I was ...
2
votes
1answer
61 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
0
votes
1answer
190 views

Comparing random access and sequential access

Assume that we choose randomly $k$ distinct numbers $N_1$, $\dots$, $N_k$ in $\{1, \dots, k\}$ and we have a file of $k$ parts. We have these two cases : We read (or write) sequentially from part ...