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)

1
vote
0answers
16 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
45 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 ...
12
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
30 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
113 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
54 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
50 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
12 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
114 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
38 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
49 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
17 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
59 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 ...
0
votes
1answer
17 views

Why are macro tapes bidirectional?

A k-macro Turing machine uses a tape which is split in blocks of k cells and works on all of them directly. After work, the head can end just beside either the right or the left end of such a block. ...
3
votes
2answers
64 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
41 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
165 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
58 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
764 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
100 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
27 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
21 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
40 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
48 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
31 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), ...
12
votes
1answer
167 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, ...
0
votes
2answers
149 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
286 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
463 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
111 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
738 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
62 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
109 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 ...
4
votes
2answers
84 views

Coq — non-terminating programs [duplicate]

People usually say Coq does not allow writing non-terminating functions. I have a question regarding that. Does Coq allow writing exactly all terminating functions? In other words, what are the ...
1
vote
2answers
175 views

What is the significance of primitive recursive functions?

I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive ...
3
votes
1answer
112 views

Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete? The set ...
6
votes
0answers
90 views

Expressiveness of modern regular expressions

I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like ...
4
votes
3answers
190 views

Can a Multi-Tape Turing Machine have an infinite number of tapes?

So if k is the number of tapes, is a multi-tape Turing machine allowed to have k = ∞ tapes. I'd assume not since this would give an infinite transition function?
4
votes
2answers
372 views

Convex Hull algorithm - why it can't be computed using only comparisons

Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that: ...
0
votes
1answer
255 views

Is there a model of computation, that tries to be realistic? [closed]

For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory. Secondly Turing machines are not really convenient IMHO for proving things ...
-1
votes
2answers
100 views

Tricky Turing Machine state diagram

what would the Turing machine state diagram be for this language: $A=\{ (0 \cup 1)^a(1 \cup 2)^b(2\cup 3)^c \mid a \geq b\} $ ? how would the turing machine design know the size of $(1 \cup 2)^b$ ? ...
-1
votes
1answer
64 views

Proving a language is context free by coming up with a context free grammar for the language [closed]

Let A and B be languages over $\sum$ = {0, 1, 2, 3} Language A = {$(0U1)^a(1U2)^b(2U3)^c | a \geq b$} Language B = {$(0U1)^a(1U2)^b(2U3)^c | a = c$} Question: prove that A and B are context free
3
votes
3answers
184 views

why is this computational method by Knuth “effective” and “powerful”?

This is a follow-up question regarding Knuth's one formulation of the concept of an algorithm here. I am asking it here because I do not have enough reputation to post a comment to that question. To ...
4
votes
1answer
119 views

Which computational model is used to analyse the runtime of matrix multiplication algorithms?

Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory ...
3
votes
1answer
236 views

How to convert a Turing Machine program to a tiling using Wang Tiles?

This is a cross-post from a post on MathSE due to lack of answers. To illustrate my question I provide the following example. The website Online Turing Machine provides a Turing Machine simulator. ...
0
votes
0answers
30 views

Recursive set - How to show a language is undecidable [duplicate]

I am currently working on the following task: A language L = {< M> | M(x) = x^2} is given. Now I need to show, that this language is not decidable. By the way, < M> is the Gödel number But ...
1
vote
1answer
96 views

Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings [closed]

The following is a homework assignment. I am looking for criticism / feedback on my solution, and I have a specific question. Suppose $L$ is a language over $\Sigma$, and $x_1, x_2, ... , x_n$ are ...
5
votes
2answers
4k views

Difference between a turing machine and a finite state machine?

I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one ...
5
votes
1answer
381 views

How to prove the structured program theorem?

Wikipedia: The structured program theorem [...] states that [...] any algorithm can be expressed using only three control structures. They are Executing one subprogram, and then another ...
1
vote
1answer
30 views

Can a loop be expressed by only the sequence of statements and the choice of statements?

The theorem of structured programming says that any algorithm can be expressed by those three control structures: Sequence Selection Iteration Isn't it possible to rewrite any loop using a finite ...