Questions tagged [computation-models]
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.
526
questions
2
votes
2
answers
919
views
Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?
An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.)
However, there are
different kind of algorithms, such as deterministic, non-...
CommunityBot
- 1
4
votes
1
answer
992
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 ...
- 277k
-2
votes
1
answer
99
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:
...
- 277k
2
votes
2
answers
766
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 -- ...
- 22.1k
9
votes
2
answers
619
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", ...
CommunityBot
- 1
5
votes
1
answer
209
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 ...
- 341
8
votes
2
answers
689
views
Can a quantum computer (theoretically) do things a classical computer (literally) can't? [duplicate]
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 ...
CommunityBot
- 1
0
votes
1
answer
78
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 constraint....
- 386
7
votes
2
answers
3k
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?
- 81
2
votes
1
answer
606
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 ...
- 72.4k
2
votes
1
answer
237
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 ...
- 1,996
6
votes
1
answer
1k
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, ...
CommunityBot
- 1
0
votes
1
answer
79
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 ...
- 361
3
votes
0
answers
134
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 ...
- 361
2
votes
2
answers
709
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 ...
11
votes
2
answers
1k
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 ...
- 11k
1
vote
1
answer
2k
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 $1$ ...
CommunityBot
- 1
3
votes
1
answer
311
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? ...
- 72.4k
2
votes
2
answers
238
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,
is ...
CommunityBot
- 1
6
votes
5
answers
2k
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 ...
CommunityBot
- 1
0
votes
3
answers
156
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 ...
- 413
2
votes
2
answers
862
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 ...
- 19.5k
-1
votes
1
answer
326
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 ...
- 72.4k
2
votes
1
answer
301
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?
- 8,308
0
votes
1
answer
532
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?
- 72.4k
1
vote
1
answer
173
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 ...
- 277k
3
votes
2
answers
550
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 spaces)...
- 29.8k
1
vote
1
answer
143
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 instance)...
- 81.7k
5
votes
0
answers
117
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 ...
- 51
1
vote
1
answer
262
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), ...
- 5,852
16
votes
1
answer
970
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, Goldstone,...
- 4,441
9
votes
1
answer
680
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 ...
- 146
6
votes
1
answer
756
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 ...
- 8,308
5
votes
5
answers
598
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 ...
- 5,390
1
vote
1
answer
683
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. ...
7
votes
2
answers
2k
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 ...
CommunityBot
- 1
1
vote
0
answers
397
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 ...
D.W.♦
- 159k
5
votes
2
answers
581
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 ...
- 72.4k
7
votes
2
answers
1k
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 ...
- 151
4
votes
1
answer
909
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 $...
- 72.4k
5
votes
2
answers
700
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:
...
- 2,926
0
votes
1
answer
278
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 ...
- 72.4k
16
votes
2
answers
1k
views
Classfication of randomized algorithms
From Wikipedia about randomized algorithms
One has to distinguish between algorithms that use the random
input to reduce the expected running time or memory usage, but always
terminate with a ...
- 277k
-1
votes
2
answers
385
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$ ? ...
- 240
-1
votes
1
answer
71
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
- 155
6
votes
3
answers
663
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 ...
CommunityBot
- 1
8
votes
1
answer
626
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 ...
- 277k
1
vote
1
answer
151
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
...
CommunityBot
- 1
0
votes
0
answers
40
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 ...
CommunityBot
- 1
7
votes
3
answers
899
views
What piece am I missing to turn this idea into a programming language?
I've been doing some reading (I'll name drop along the way) and have selected a few scattered ideas that I think could be cobbled together into a nifty esoteric programming language. But I'm having ...
- 277