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)

4
votes
1answer
79 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
16 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 ...
-1
votes
1answer
60 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
0answers
42 views

primitive recursive set and some challenge? [closed]

I ran into a Interview Question on P.hD entrance. if g be a primitive recursive, and $f_1(0)=c_1, f_1(1)=c_2, f_1(x+2)=g(x,f_1(x),f_1(x+1))$ and $f_2(x)=c, f_2(x+1)=g(x,[f_2(0),...,f_2(x)])$ ...
-1
votes
0answers
60 views

convert base 2 into base 10 by a one state Turing machine

I've got the following exercise to do, I'm sitting there since monday and I'm somehow stuck. I should invent a Turing machine which converts a binary number into a decimal one. Here you will make one ...
2
votes
2answers
55 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
124 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
28 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
91 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
38 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
81 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, ...
3
votes
2answers
121 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
83 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
27 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
27 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 ...
5
votes
2answers
99 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
52 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
20 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 ...
4
votes
2answers
73 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 ...
13
votes
6answers
3k 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
49 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
134 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
60 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 ...
2
votes
2answers
65 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
22 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
117 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
46 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
58 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
22 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
65 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
73 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, ...
2
votes
3answers
45 views

Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question: "This question is about recursion. A recursive method can always be implemented by an iterative method ...
3
votes
2answers
180 views

Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape ...
1
vote
1answer
70 views

Are conditionals necessary in computation? [duplicate]

I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for ...
6
votes
6answers
824 views

Do turing machines assume something infinite at some point?

In a previous question What exactly is an algorithm? , i asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm. One of the ...
4
votes
5answers
118 views

Are if statements unnecessary if a program is represented as an explicit state machine?

This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation. Consider a program that manages a ...
0
votes
0answers
37 views

Simulating two dimensional tape TM with ordinary two tape TM

So I know that any multiple tape Turing Machine can be simulated with the one tape TM. But what about if we have a two dimensional tape TM? Can it be simulated with the ordinary two tape TM? Will they ...
0
votes
1answer
23 views

Computing composite functions

This may not be strictly a computer science question but is related. Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is ...
4
votes
0answers
44 views

Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
1
vote
0answers
72 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM ...
1
vote
1answer
32 views

Is random access allowed in the Bit Complexity model, or is it just expensive?

In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word). In the Bit Complexity model (no wiki article, sorry), ...
13
votes
1answer
191 views

Quantum Computing - Relationship between Hamiltonian and Unitary model

When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, ...
1
vote
2answers
70 views

How does an automaton model a computer or something else?

An automaton, as I have seen so far, is used to tell if a string belongs to the language that the automaton recognizes. This is determined by the final state of the automaton running on the string as ...
0
votes
2answers
181 views

Theory of computation introductory curriculum

I want to study theory of computation on my own, so I am looking for books. What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation? ...
5
votes
1answer
303 views

Is model theory useful for computer scientists

It is often stated in the CS folklore that Turing was inspired by Gödel's incompleteness theorem, more specifically the diagonalization proof and the isomorphism between axiomatically generated ...
4
votes
5answers
471 views

Can we use domains other than the naturals in computability theory?

I wonder why people assume the domain of a computable function is $\mathbb N$? For example, in Wikipedia. Can its domain be any countable set rather than $\mathbb N$? Can its domain be an ...
1
vote
1answer
113 views

Is there a problem that cannot be represented using graph?

It is obvious that the representational power of graphs are huge. Is there a problem that cannot be represented using graph? I have recently asked this question to my students and no answers came up. ...
5
votes
2answers
758 views

Can we represent all computer programs as graphs?

I was thinking the other day, and it occurred to me that computer programs all seem to be representable as a graph (an abstract syntax tree for example), or, once common expressions are combined, an ...
1
vote
0answers
67 views

Reducing states in a finite-state machine using compatibility classes, for an incompletely specified machine

In the process of reducing the states of a synchronous finite state machine first we need to create maximal compatibility classes (of states; which states can be compatible, i.e. the "don't cares" can ...
4
votes
1answer
121 views

Relation between RAM and Turing machine

Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers ...