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)

0
votes
0answers
18 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
26 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
52 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
90 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
50 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 ...
0
votes
1answer
24 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 ...
8
votes
0answers
56 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
37 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
63 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
25 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
15 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
133 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
105 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
59 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
37 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
619 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
245 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
54 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
94 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
121 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
66 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
161 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
32 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
99 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
102 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, ...
4
votes
2answers
149 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
140 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
29 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
41 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
143 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
53 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
22 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
136 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
59 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
165 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 ...
0
votes
3answers
64 views

Where does the need for conditionals (if, switch, jump tables, etc…) truly arise? [duplicate]

I know that this question is a bit out-of-the-box, yet i would be glad if someone could help with a good answers for my question because it is something that is troubling my curious mind. When we ...
3
votes
2answers
92 views

Can a petri net fire only one transition at a single moment?

After reading several articles about petri nets, I am confused on how firing works. Can Petri net system fire only one transition out of all active (fire-able transitions) at a single moment? Or are ...
-1
votes
1answer
42 views

Cocurrent programming language being Turing-equivalent and difference between Turing-complete and equivalent

In Is concurrent language CCS or CSP turing-equivalent in language power?, the answer says that CCS or CSP is Turing-complete. But that does not seem to answer whether CCS or CCP is Turing-equivalent. ...
-1
votes
1answer
120 views

Proving equivelance of a multijump turing machine and a turing machine

I'm having trouble getting started on this proof, and I was hoping you guys could give me a couple hints/point me in the direction of where to start? Here's the problem: Consider a multijump Turing ...
2
votes
1answer
58 views

Is concurrent language CCS or CSP turing-equivalent in language power?

Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines? Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?
0
votes
1answer
65 views

Simulate a regular Turing Machine with one that cannot write blanks

Consider a Turing machine that cannot write blanks. How does one show that such a machine can simulate a standard Turing machine?
1
vote
1answer
26 views

Can we obtain a state diagram of a single Turing machine

When illustrating what states are in Turing machine, often the examples of programs, like a checker that checks an input number is even number, are given. But different programs seem to have different ...
2
votes
2answers
75 views

How is the number of states in a Turing machine bounded?

The definition of Turing machine says that the number of states is finite. However, I do not get how this can be true. Is the number of states in a Turing machine actually not fixed, that is not ...
3
votes
2answers
81 views

Is Newton's Method to compute the zeros of a function an algorithm?

Looking for Newton's method in Wikipedia, I read the following: In numerical analysis, Newton's method (also known as the Newton-Raphson method), named after Isaac Newton and Joseph Raphson, ...