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)

-2
votes
1answer
53 views

How can a Turing machine accept infinite number of inputs?

How it is possible for a turing machine to process an infinitely long input ?
3
votes
0answers
25 views

A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
1
vote
2answers
42 views

Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- ...
1
vote
1answer
36 views

PRAM with no bit operations and P vs NC

I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition ...
56
votes
1answer
6k views

What does the “Lambda” in “Lambda calculus” stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the ...
4
votes
0answers
28 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel ...
5
votes
2answers
72 views

What theorem are these? (from Scott Aaronson's blog)

Browsing Scott Anderson's blog, I found this list of theorem. Among them are: If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a ...
1
vote
2answers
83 views

Can one consider living (biological) cell to be Turing Complete?

Universal Turing Machine can be boiled down to two components. Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending ...
2
votes
1answer
31 views

Prove that the Kolmogorov complexity function cannot be approached from below

How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function? After some research it seems I must show the function $K(x)$ is not lower ...
3
votes
2answers
121 views

Why classification represents all computations?

I'm a computer science student taking a theory of computation class. Recently we were taught about what is computable and what is not and about the Turing machine. As I understood (please correct me ...
1
vote
1answer
53 views

Non deterministic turing machine

Does a non deterministic turing machine which is a decider halt on all branches for all inputs?? I know it must halt on all branches for a string not in language but for a string in language ,NDTM ...
3
votes
1answer
19 views

Maximal class for which function equivalence is decidable

I previously asked if it's decidable whether two primitive recursive functions are equivalent: "primitive recursive functional equivalence". The answer was no. Here is my followup. What is the most ...
0
votes
1answer
9 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
40
votes
7answers
10k views

Is there anything that MUST be done on a multi-core CPU?

When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing ...
1
vote
0answers
19 views

About the SOS degree of a function and optimization algorithms for the function

Given a non-negative function on the hypercube $f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$ one says that it is of "SOS-degree" of $d$ (denoted as $deg_{SOS}(f) =d$) if $d$ is the minimum $k$ such ...
1
vote
2answers
43 views

Turing machine that can tell if it ends in standard position?

Suppose we have a TM $M$ with alphabet $\{0, 1 \}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape ...
1
vote
1answer
64 views

Why is universal turing machine considered with only one head?

While defining the following time hierarchy theorem (for deterministic case ) : If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$ ...
1
vote
1answer
68 views

Explanation for indirect addressing

While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump. ...
4
votes
0answers
53 views

Advances in recent time in Von-neumann self replication idea

I have read about Von-neumann self replication from Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing ...
1
vote
2answers
239 views

Turing machine - infinite tape - does that thing exist?

Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist? Do we have the right to regard a machine (a construct) in the same ...
1
vote
0answers
40 views

What can be said about the Halting Problem if we can include the halting status to the input?

I was reading about Turing Machines and the Halting Problem, i understand that you need an oracle to decide whether given input will halt or loop forever. But why do we need an oracle if we can ...
5
votes
0answers
101 views

Computational power of Actor Model

In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine. In his paper "Actor Model of Computation: Scalable Robust Information ...
1
vote
1answer
44 views

Can computation models be categorized in terms of efficiency?

It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other ...
0
votes
3answers
112 views

Can a Turing Machine have infinite accept states?

I'm still fairly new to Turing Machines, but I've been doing some research. I know that a Turing Machine can have an infinite tape and that it requires a finite number of states, but does it ...
5
votes
3answers
73 views

What does it mean to be “independent of machine model”?

I have often heard people mention off-hand that the class $\mathsf{P}$ is "machine-independent", or "independent of machine model", or "invariant under change of machine model" - something to do with ...
2
votes
0answers
41 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions ...
2
votes
0answers
57 views

Differences between programming model and programming paradigm?

What is the relation and difference between a programming model and a programming paradigm? (especially when talking about the programming model and the programming paradigm for a programming ...
2
votes
1answer
65 views

A model of computation vs an abstract machine

Wikipedia says A model of computation is a formal description of a particular type of computational process. The description often takes the form of an abstract machine that is meant to perform ...
1
vote
1answer
227 views

Can a Turing machine have infinite states?

Does it make sense for a Turing machine to have infinite number of states ? I had previously asked a question Can Turing machines have infinite length input. From which I came to know about Type-2 ...
19
votes
8answers
7k views

Programming language where every expression makes sense

Per recommendation I am reposting this from Stack Overflow. Recently I have been thinking about following issue. Consider the code for a standard "Hello world!" program: ...
3
votes
1answer
37 views

Is modulus capable of universal computation?

I heard once that you could translate any digital circuit into a modulus operation, perhaps modulusing against different numbers? It was a long while ago though and don't remember where I heard it. ...
2
votes
1answer
49 views

Are Cellular Automata always computers?

I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer. In the introduction part: Cellular automata can be ...
1
vote
1answer
193 views

In principle, what is the relation between Artifical Intelligence and Turing machine?

I am working on my cs project about AI & Turing machines, so i know that Artifical Intelligence is meant to implement different algorithms into the machine {the computer} to solve a problem or a ...
2
votes
7answers
94 views

Is infinitely fast computer fundamentally impossible even theoretically?

This may get slightly philosophical, but consider the following program: ...
8
votes
1answer
308 views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
4
votes
1answer
54 views

Generative power and classification of matrix grammars

[Edited] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy. In here it is stated that: A matrix ...
12
votes
3answers
261 views

What specifically makes quantum computers useful?

I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic. That seems to be what people point to as being what makes quantum ...
4
votes
2answers
61 views

How Cellular Automata is related to Automata Theory?

I have read about Automata Theory where it is about the study of abstract machines and automata. And i know that an abstract machine takes the input, process it and create the output, just like ...
3
votes
3answers
79 views

Computational problem - definition

How should I understand the definition of computational problem? A computational problem is a mathematical object representing a collection of questions that computers might be able to solve. ...
4
votes
0answers
20 views

Computational complexity of emulating (untyped) λ-calculus with a queue machine

I am looking for bounds - both lower and upper - on the time, spacial, and state/symbol (i.e. number of states and symbols required) complexity of simulating the (untyped) λ-calculus with a queue ...
2
votes
0answers
16 views

Complexity bounds for Turing equivalence [closed]

I am looking for bounds - both lower and upper - on the time and spacial complexity of simulating Turing-complete systems with each other. (I am aware that both time and space are ill-defined with ...
5
votes
2answers
135 views

How to prove universality in complex systems?

I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once. The ...
2
votes
1answer
122 views

Does solving mathematical equations with Cellular Automata structures means it is universal?

I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure. The ...
0
votes
0answers
13 views

Total Turing Machine Grammar [duplicate]

We know that the Turing Machine corresponds to the 'Unrestricted' set of grammars. To what set of grammars does the Total Turing Machine correspond?
0
votes
1answer
55 views

Quantum computer memory size

Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers). Does it also hold for memory size? Are QC going to have ...
10
votes
3answers
1k views

Infinite calculations in finite time

This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to ...
6
votes
2answers
124 views

Are Elementary Cellular Automata structures considered to be fractals?

I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata. But, what about the other rules from ...
7
votes
3answers
208 views

Why is the tape not part of the definition of a Turing Machine?

I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, ...
2
votes
1answer
50 views

Chomsky hierarchy type determined by language

I have some modified automata and the task is to give the type of Chomsky hierarchy to it. All task is between type 3 and 0 noninclusive. For regular languages there are lot of tools and I can check ...
14
votes
5answers
4k views

Why is a quantum computer not capable of solving more problems than a classical computer?

On the Wikipedia page for quantum algorithm I read that [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are ...