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
votes
0answers
29 views

ice (sleet, glaze ice) [on hold]

I must to forecast an ice (sleet, glaze ice). I have base of data with parameters to predict, but this data base have not some parametres. In one day I have three parametres in other day I have four ...
-1
votes
0answers
39 views

Why these restrictions on the input alphabet of Turing machines?

Recently, I am learning about the definition of Turing machine. When I read the following sentence: ``Each machine $M$ has a specified input alphabet $\Sigma$, which is a subset of $\Gamma$, not ...
4
votes
0answers
35 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
41 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
30 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
155 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
128 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
267 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
461 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
108 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
709 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
58 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
75 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
74 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
143 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
93 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 ...
5
votes
0answers
83 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
157 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
360 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
254 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
82 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
62 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
175 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
108 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
141 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
86 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 ...
4
votes
2answers
2k 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
304 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
28 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 ...
5
votes
1answer
50 views

Tag system variant

Is there an "official" name for this slight variant of the well known Tag System model of computation, and/or has it been used somewhere? a finite alphabet of symbols $\Sigma$ a halt symbol $H$ an ...
5
votes
0answers
72 views

Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
6
votes
2answers
162 views

Automaton equivalent of the π calculus?

If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing ...
1
vote
1answer
78 views

In the “tall cache assumption” what does $\Omega$ represent?

Within the field of cache-oblivious algorithms the ideal cache model is used for determining the cache complexity of an algorithm. One of the assumptions of the ideal cache model is that it models a ...
0
votes
0answers
100 views

The complement of the acceptance problem reduces to the acceptance problem: ${A_{TM}}{ \le _M}\overline {{A_{TM}}} $ is this claim true?

If ${A}{ \le _M} {{B}} $ then $\overline A { \le _M}\overline B$ since the mapping reduction function is computable. So, if ${A_{TM}}{ \le _M}\overline {{A_{TM}}} $ then $\overline{A_{TM}}{ \le _M} ...
1
vote
0answers
248 views

Difference between Analytical and Difference Engines

I'm not sure if one can compare the two, mainly because what I've read so far, I didn't quite understand, but what are the key differences between these 2 engines?
0
votes
1answer
144 views

construct a TM from a PDA

Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$. My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add ...
5
votes
2answers
131 views

Is there an always-halting, limited model of computation accepting $R$ but not $RE$?

So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages. I'm wondering, is ...
8
votes
2answers
148 views

Which theoretical parallel model is closest to CUDA?

Which theoretical parallel model is closest to CUDA/OpenCL programming model? For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too ...
4
votes
1answer
303 views

Parallel merge sort using hypercube connection template

I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear. What I ...
4
votes
2answers
467 views

Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?

Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar? I don't believe this has a context-free grammar, but please correct me if I'm wrong.
3
votes
2answers
64 views

Matching Lemma with infinitely many symbols

I was reading about Universal Turing Machines. I see that the matching lemma states, that between two symbols X and Y, if there are only 1-s and blanks, then a TM exists, which can count the number ...
5
votes
4answers
656 views

What is the exact relation between programming languages and Turing machines?

I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, ...
1
vote
0answers
270 views

λ-Calculus extensions: meaning of extension symbols

When working with λ-Calculus I see lots of extensions that use other symbols such as ∀ <:Top {} ←, which are from "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce. ...
0
votes
3answers
126 views

Looking for some more details on “Turing” devices

I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I ...
4
votes
2answers
533 views

Models of computation: the arithmetic model, Turing machine (and …)

How is an arithmetic model defined? What relations are between it and Turing machine? Are they equivalent in some sense? Is it true that in the arithmetic model of computation, the basic ...
7
votes
1answer
191 views

Does forcing TMs to change all symbols they read change their power?

If we limit a turing machine so that it is not allowed to write the symbol that it reads would it reduce its power? For example: $( State, A, State, Z, DIRECTION)$ $A$ cannot be the same symbol as ...
1
vote
1answer
451 views

How can one simulate a PDA with a FIFO queue PDA?

I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most ...
6
votes
2answers
219 views

Mathematical model on which current computers are built

It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists ...
3
votes
2answers
167 views

Robustness of Turing Machines - 3 dimensional case

How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from ...