Computation: Finite and Infinite Machines

By Marvin Minsky. 1967

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Neural Turing Machines (2014, background): “” Rapidly-created variables (Hadley, 2009) are data that are quickly bound to memory slots, in the same way that the number 3 and the number 4 are put inside registers in a conventional computer and added to make 7 (Minsky, 1967).”
On the computational power of neural nets (1992, background): “Minsky proved the existence of a universal Turing Machine having one tape with 4 letters and 7 control states, [19].”
Integration of nanoscale memristor synapses in neuromorphic computing architectures (2013, background): “(Some figures may appear in colour only in the online journal)”
Why AI is harder than we think (2021, background): “the problems of creating ‘artificial intelligence’ will be substantially solved” [12].”
Spiking Neural P Systems (2006, background): “, [9]) that register machines (even with a small number of registers, but this detail is not relevant here) compute all sets of numbers which are Turing computable, hence they characterize NRE.”
A survey of computational complexity results in systems and control (2000, methodology): “For textbook treatments, we refer the reader to Minsky (1967), Aho, Hopcroft and Ullman (1974), Garey and Johnson (1979), Hopcroft and Ullman (1979), Davis (1982) and Papadimitriou (1994).”
Computational Mechanics: Pattern and Prediction, Structure and Simplicity (1999, unknown): “Since we can convert from one such device to another—say, from a Post tag system [41] to a Turing machine—with only a finite description of the first system, such constants are easily assimilated when measuring complexity in this approach.”
Evolution , Ecology and Optimization of Digital Organisms (1992, methodology): “Sets of machine instructions similar to those used in the Tierra Simulator have been shown to be capable of “universal computation” ([2, 24, 26]).”
The Neural Network Pushdown Automaton: Architecture, Dynamics and Training (1997, background): “To enhance the computational power of a recurrent neural network finite state automaton to that of aninfinite machine [Minsky67] requires an expansion of resources.”
Swarm robotics: a review from the swarm engineering perspective (2013, methodology): “One of the most adopted design methods to obtain such behaviors is the use of a particular class of finite state machine (Minsky 1967): probabilistic finite state machines (PFSMs).”