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 ...


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.


11

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a longstanding open problem. The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs ...


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 ...


7

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 ...


7

It appears that all of these operations can be performed in time $O(\log n/\log\log n)$ on a RAM, by combining methods for maintaining a dynamic labeling of the list elements by integers of polynomial magnitude (e.g. Bender et al, "Two Simplified Algorithms for Maintaining Order in a List", ESA 2002, https://erikdemaine.org/papers/DietzSleator_ESA2002/) with ...


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

(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few. Might it be the case that a RAM program can solve general CNF-SAT in exponential time with a base less than 2, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base ...


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 ...


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

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

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 ...


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

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

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

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 will start with an overall comparison of essentially linear v quasilinear, and then give a specific example of the requested computational models. As an equivalence relation, quasilinear time (denoted using $\tilde{O}$) is the most fine-grained measure that is robust between a number of different sequential deterministic models. By contrast, essentially ...


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

$\newcommand\Ptime{\mathsf P} \newcommand\NP{\mathsf{NP}} \newcommand\poly{\mathsf{poly}}$ It is known that $\Ptime/\poly \neq \NP/\poly \implies \Ptime_{\mathbb C}\neq \NP_\mathbb{C}$ [1] where the latter two represent the classes $\Ptime$ and $\NP$ in the BSS model over the complex numbers. (You can take the contrapositive to obtain a consequence of $\...


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

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

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

Your description looks correct. The equivalence between deterministic models (under essentially linear time translation) for algorithms using $t^{o(1)}$ space (if the input size is $t^{o(1)}$ or we have random access to the input) is a nice observation. (However, we do know yet know whether randomized algorithms might be faster (even for $t^{o(1)}$ input ...


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

Here's one interpretation of your question, which you may or may not have intended, but for which I have an answer. Computers are obviously real physical devices and therefore can be modeled by the laws of physics. But we don't use the laws of physics that would be needed to describe a real computer as a model of computation because it's too complex. To ...


2

Short answer: yes. Long answer: Using process algebra as a witness to the claimed existential is certainly admissible, but the way the question is phrased might warrant are more direct answer. If TMs are used as mathematical model for sequential computation, we can surely come up with a concurrent version, and show that it is no more powerful than the good ...


2

The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of Handbook of Theoretical Computer Science, Vol. A. For simulations between RAM and Turing machines see Theorems 2.5 and 2.6, pp. 26--27. It also contains pointers to historic references.


2

research into GPU algorithms continues and it is well suited to some problems, but some of the initial excitement may be wearing off after lackluster results and difficulty of translating problems into GPU approaches. also in recent times there is some consternation over transfer overhead to/ from the GPU. from anecdotal/ background stories/ conversations ...


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