# Tag Info

75

Here's my favorite analogy. Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because Turing machines can't toast bread. Therefore, you need my revolutionary new model, the Toaster-Enhanced Turing Machine (TETM), which allows ...

35

I think the issue is quite simple. All interactive formalisms can be simulated by Turing machines. TMs are inconvenient languages for research on interactive computation (in most cases) because the interesting issues get drowned out in the noise of encodings. Everybody working on the mathematisation of interaction knows this. Let me explain this in more ...

26

In terms of number computability (i.e., computing functions from $\mathbb{N} \to \mathbb{N}$), all known models of computation are equivalent. However, it's still true that Turing machines are fairly painful for modelling properties like interactivity. The reason is a little bit subtle, and has to do with the kinds of questions that we want to ask about ...

23

Yes, it is. Here's how you do it: You can compile basically any program you like to circuits. See for instance the work of Dan Ghica and his collaborators on the Geometry of Synthesis, which shows how to compile programs into circuits. Dan R. Ghica. Geometry of Synthesis: A structured approach to VLSI design Dan R. Ghica, Alex Smith. Geometry of Synthesis ...

21

It's a little vague, but I like the question. I wrote a paper about it a LONG time ago. Maybe this will help the Anonymous questioner: Brute Force Search and Oracle-Based Computation Here's a summary. Informally, if you do not keep any scratch work from previous trials, and just try all possible solutions in lexicographical order until a desired ...

21

Can such machines be built in practice? Yes. By "machine", Schmidhuber just means "computer program". Are they at least feasible in our Universe? Not in their current form -- the algorithms are too inefficient. From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of ...

16

Meyer auf der Heide described a non uniform family of linear decision trees for Subset Sum with depth $O(n^4\log n)$. A similar result can be deived from a later algorithm of Meiser for point location in hyperplane arrangements. Of course the problem is NP-hard.

8

The paper you mention is probably one of Paul Vitányi's, possibly Time, Space, and Energy in Reversible Computing. However, not everyone takes the viewpoint that simulation of irreversible computations is the main point. There is some research into what reversible computing can do in addition to such simulations, the beginnings of which is in Bennett's ...

8

Is it due to Sipser? Or Penrose? Sorry, that made me laugh out loud. Penrose? Today's notion of formal language (a language is a set of words or strings) can be traced at least as far back as Frege in the late 1800's and Thue in the early 1900's. Chomsky's 1956 paper was very influential, and definitely uses the term "language" for a set of strings. ...

7

I essentially agree with Martin's comment, I can elaborate on that to make a tentative answer, knowing that there is no general formal definition of calculus or abstract machine and that what I am going to describe cannot possibly cover the meaning of all instances of these two words found in the literature. In brief: a calculus usually gives you the ...

6

Ryan Williams surveyed and studied the complexity of reversibility in this paper, space efficient reversible simulations which contains various constructions. The problem seems to be closely linked to lower bounds on time/space tradeoffs.. In your question you seem to be making some kind of distinction between "reversibility" and "direct reversibility" but ...

6

Just an extended comment, for those who didn't notice that "This guy" in the question is not the author of the linked blog, but refers to Gregory Chaitin. The sentence is from the lecture: A Century of Controversy over the Foundations of Mathematics; the transcription can be found here. It seems interesting (I'm going to read it now)! ... Okay, I'd like ...

6

Membrane Computing is a model that is based on the possibility or not of movement of molecules through membranes; also on possible reactions of these molecules inside a membrane compartment. While this is not specifically talking about proteins, in reality some of these molecules and the channels through which they pass would be proteins. Here is an ...

5

In 1936, Konrad Zuse developed what was for all intents and purposes the Z1 the first computer in the modern sense. This fact is little known but has since been acknowledged even by his international competitors, e.g. IBM. While the Z1 was not very reliable, later models (still developed during WWII) actually worked. Shortly after the war, Zuse's company ...

5

A practical example of this is the Tic Tac Toe computer made out of Tinker Toys at the Boston Science Museum (originally made by a team of MIT students). Of course, this is much simpler than Microsoft Word. Here is a 1989 article from Scientific American describing it. There have also been Turing machines made out of legos (this cheats a bit because it ...

5

I can see his point, but I think he's really (deliberately?) confusing computation (and the mathematics thereof) and computers. A computer is certainly a device for performing computation, but what Church and Turing created was a (well, two, but they're "the same") theoretical (read mathematical) model of the process of computation. That is, they define a ...

5

Your question (1) is essentially the difference between Turing machines that recognize languages and Turing machines that compute functions. This difference is essential for proving theorems about complexity classes like NP. And in fact, if we look at Cook's 1971 paper The Complexity of Theorem-Proving Procedures, which proved the Cook-Levin theorem, we find ...

4

I have realized one very good example: Langton's ant. It is reversible. It also does not seem to be a "forced" reversibility model – ie. it is not the "keep input history" approach: $f(a) \rightarrow (a,f(a))$. It also is universal.

4

Functions can be partially applied, so you can end up with a situation in which a function is called with "not enough" arguments. For example, consider the map functional: (* map : ∀α,β. (α → β) → list α → list β *) let rec map f xs = match xs with | [] -> [] | x :: xs -> (f x) :: map f xs This will take a function f as an argument, and ...

4

That is a defensible position to take. "Computational devices" existed before Turing. The idea that Turing had that was so powerful in the development of real computers was the idea of a "universal computer": i.e. a single piece of hardware that could perform any calculation by taking as input data that described a different machine -- software. This kind of ...

4

Here is an example of a trivial gap between decision-tree and algorithmic complexity. The randomized decision tree complexity of local sorting (orienting a vertex-weighted graph) is $O(n\log(\frac{m+n}{n}))$ whereas the size of the input is $\Theta(n+m)$. Any algorithm needs to read the input, so there's a separation whenever $m=\omega(n)$. See Goddard, ...

4

I view this question as one in the history of Turing machine theory, which indeed has had more changes than are evident from contemporary textbooks. The Turing model of 1936 was remarkably different from the later more accepted formulations. In more detail in terms of your questions: (1),(2) The modern formulation in terms of Recogniser, and Languages ...

4

I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words ...

3

As already suggested above, process algebra or process calculus is the place to start. Quoting freely from the respective Wikipedia page, History In the first half of the 20th century, various formalisms were proposed to capture the informal concept of a computable function, with μ-recursive functions, Turing Machines and the lambda calculus ...

3

There's a comprehensive treatment of different Turing-complete computation models and proofs of their equivalence in Martin Davis, Computability and Unsolvability. Some of the most popular systems are described, including Turing-Machines, Post problems and general recursive functions.

3

Fredkin Gate and Toffoli Gate are two examples of reversible computation in that no information is lost in this process and then according to Boltzman Entrophy Law energy is at least not comsumed. Fredkin Gate and Toffoli Gate can simulate NAND gate and FANOUT, thus simulating any classical circuit. Cook-Levin theorem indicates that classical circuits can ...

3

Look at the " $U$s " in the first table of the paper "Small Turing Machines ...". For example, 2 states and 18 symbols are enough to build a Turing Machine that can execute an operating system (if you augment it with an adequate I/O mechanism :) ... If you look for small models closer to the Von Neumann architecture then take a look at Random-access stored-...

3


3

As others have pointed out, "model of computation" is an open-ended concept that can hardly be captured by a single defintion. A similar example in traditional mathematics is "space". However, this should not prevent us from giving precise definitions of "model of computation". As our understanding and motivations change, so will the definitions. And keep ...

2

There does indeed exist a category theoretic description of cellular automata. I don't know the details, but I can provide you with a reference. It doesn't look like an easy description, though. S. Capobianco, T. Uustalu. A categorical outlook on cellular automata. In J. Kari, ed., Proc. of 2nd Symp. on Cellular Automata, JAC 2010 (Turku, Dec. 2010), v. 13 ...

Only top voted, non community-wiki answers of a minimum length are eligible