Gödel numbering

From Wikipedia, the free encyclopedia

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was used by Kurt Gödel for the proof of his incompleteness theorems. (Gödel 1931)

A Gödel numbering can be interpreted as an encoding in which a number is assigned to each symbol of a mathematical notation, after which a sequence of natural numbers can then represent a sequence of symbols. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic.

Since the publishing of Gödel's paper in 1931, the term "Gödel numbering" or "Gödel code" has been used to refer to more general assignments of natural numbers to mathematical objects.

Simplified overview

Gödel noted that statements within a system can be represented by natural numbers. The significance of this was that properties of statements - such as their truth and falsehood - would be equivalent to determining whether their Gödel numbers had certain properties. The numbers involved might be very long indeed (in terms of number of digits), but this is not a barrier; all that matters is that we can show such numbers can be constructed.

In simple terms, we devise a method by which every formula or statement that can be formulated in our system gets a unique number, in such a way that we can mechanically convert back and forth between formulas and Gödel numbers. Clearly there are many ways this can be done. Given any statement, the number it is converted to is known as its Gödel number. A simple example is the way in which English is stored as a sequence of numbers in computers using ASCII or Unicode:

• The word HELLO is represented by 72-69-76-76-79 using decimal ASCII.
• The logical statement x=y => y=x is represented by 120-61-121-32-61-62-32-121-61-120 using decimal ASCII.

Gödel's encoding

Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing.

To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence ${\displaystyle (x_{1},x_{2},x_{3},...,x_{n})}$ of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence:

${\displaystyle \mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.}$

According to the fundamental theorem of arithmetic, any number (and, in particular, a number obtained in this way) can be uniquely factored into prime factors, so it is possible to recover the original sequence from its Gödel number (for any given number n of symbols to be encoded).

Gödel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the key observation of the proof.

There are more sophisticated (and more concise) ways to construct a Gödel numbering for sequences.

Example

In the specific Gödel numbering used by Nagel and Newman, the Gödel number for the symbol "0" is 6 and the Gödel number for the symbol "=" is 5. Thus, in their system, the Gödel number of the formula "0 = 0" is 2⁶ × 3⁵ × 5⁶ = 243,000,000.

Lack of uniqueness

A Gödel numbering is not unique, in that for any proof using Gödel numbers, there are infinitely many ways in which these numbers could be defined.

For example, supposing there are K basic symbols, an alternative Gödel numbering could be constructed by invertibly mapping this set of symbols (through, say, an invertible function h) to the set of digits of a bijective base-K numeral system. A formula consisting of a string of n symbols ${\displaystyle s_{1}s_{2}s_{3}\dots s_{n}}$ would then be mapped to the number

${\displaystyle h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.}$

In other words, by placing the set of K basic symbols in some fixed order, such that the i^th symbol corresponds uniquely to the i^th digit of a bijective base-K numeral system, each formula may serve just as the very numeral of its own Gödel number.

For example, the numbering described here has K=10000.

Application to formal arithmetic

Recursion

One may use Gödel numbering to show how functions defined by course-of-values recursion are in fact primitive recursive functions.

Expressing statements and proofs by numbers

Once a Gödel numbering for a formal theory is established, each inference rule of the theory can be expressed as a function on the natural numbers. If f is the Gödel mapping and if formula C can be derived from formulas A and B through an inference rule r; i.e.

${\displaystyle A,B\vdash _{r}C,}$

then there should be some arithmetical function g_r of natural numbers such that

${\displaystyle g_{r}(f(A),f(B))=f(C).}$

This is true for the numbering Gödel used, and for any other numbering where the encoded formula can be arithmetically recovered from its Gödel number.

Thus, in a formal theory such as Peano arithmetic in which one can make statements about numbers and their arithmetical relationships to each other, one can use a Gödel numbering to indirectly make statements about the theory itself. This technique allowed Gödel to prove results about the consistency and completeness properties of formal systems.

Generalizations

In computability theory, the term "Gödel numbering" is used in settings more general than the one described above. It can refer to:

1. Any assignment of the elements of a formal language to natural numbers in such a way that the numbers can be manipulated by an algorithm to simulate manipulation of elements of the formal language.
2. More generally, an assignment of elements from a countable mathematical object, such as a countable group, to natural numbers to allow algorithmic manipulation of the mathematical object.

Also, the term Gödel numbering is sometimes used when the assigned "numbers" are actually strings, which is necessary when considering models of computation such as Turing machines that manipulate strings rather than numbers.

Gödel sets

Gödel sets are sometimes used in set theory to encode formulas, and are similar to Gödel numbers, except that one uses sets rather than numbers to do the encoding. In simple cases when one uses a hereditarily finite set to encode formulas this is essentially equivalent to the use of Gödel numbers, but somewhat easier to define because the tree structure of formulas can be modeled by the tree structure of sets. Gödel sets can also be used to encode formulas in infinitary languages.

Computable function

From Wikipedia, the free encyclopedia

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions. Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the μ-recursive functions.

Before the precise definition of computable function, mathematicians often used the informal term effectively calculable. This term has since come to be identified with the computable functions. Note that the effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases exponentially (or even superexponentially) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently.

According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that a function is computable if and only if it has an algorithm. Note that an algorithm in this sense is understood to be a sequence of steps a person with unlimited time and an unlimited supply of pen and paper could follow.

The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory, the problem of determining the complexity of a computable function is known as a function problem.

Definition

Computability of a function is an informal notion. One way to describe it is to say that a function is computable if its value can be obtained by an effective procedure. With more rigor, a function ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ is computable if and only if there is an effective procedure that, given any k-tuple ${\displaystyle \mathbf {x} }$ of natural numbers, will produce the value ${\displaystyle f(\mathbf {x} )}$.^[1] In agreement with this definition, the remainder of this article presumes that computable functions take finitely many natural numbers as arguments and produce a value which is a single natural number.

As counterparts to this informal description, there exist multiple formal, mathematical definitions. The class of computable functions can be defined in many equivalent models of computation, including

• Turing machines
• μ-recursive functions
• Lambda calculus
• Post machines (Post–Turing machines and tag machines).
• Register machines

Although these models use different representations for the functions, their inputs and their outputs, translations exist between any two models, and so every model describes essentially the same class of functions, giving rise to the opinion that formal computability is both natural and not too narrow.^[2]

For example, one can formalize computable functions as μ-recursive functions, which are partial functions that take finite tuples of natural numbers and return a single natural number (just as above). They are the smallest class of partial functions that includes the constant, successor, and projection functions, and is closed under composition, primitive recursion, and the μ operator.

Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ can be calculated if and only if there exists a computer program with the following properties:

1. If ${\displaystyle f(\mathbf {x} )}$ is defined, then the program will terminate on the input ${\displaystyle \mathbf {x} }$ with the value ${\displaystyle f(\mathbf {x} )}$ stored in the computer memory.
2. If ${\displaystyle f(\mathbf {x} )}$ is undefined, then the program never terminates on the input ${\displaystyle \mathbf {x} }$.

Characteristics of computable functions

The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute the function. The models of computation listed above give different interpretations of what a procedure is and how it is used, but these interpretations share many properties. The fact that these models give equivalent classes of computable functions stems from the fact that each model is capable of reading and mimicking a procedure for any of the other models, much as a compiler is able to read instructions in one computer language and emit instructions in another language.

Enderton [1977] gives the following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing [1936], Rogers [1967], and others.

• "There must be exact instructions (i.e. a program), finite in length, for the procedure."

Thus every computable function must have a finite program that completely describes how the function is to be computed. It is possible to compute the function by just following the instructions; no guessing or special insight is required.

• "If the procedure is given a k-tuple x in the domain of f, then after a finite number of discrete steps the procedure must terminate and produce f(x)."

Intuitively, the procedure proceeds step by step, with a specific rule to cover what to do at each step of the calculation. Only finitely many steps can be carried out before the value of the function is returned.

• "If the procedure is given a k-tuple x which is not in its domain of f, then the procedure might go on forever, never halting. Or it might get stuck at some point (i.e., one of its instructions cannot be executed), but it must not pretend to produce a value for f at x."

Thus if a value for f(x) is ever found, it must be the correct value. It is not necessary for the computing agent to distinguish correct outcomes from incorrect ones because the procedure is always correct when it produces an outcome.

Enderton goes on to list several clarifications of these 3 requirements of the procedure for a computable function:

1. The procedure must theoretically work for arbitrarily large arguments. It is not assumed that the arguments are smaller than the number of atoms in the Earth, for example.
2. The procedure is required to halt after finitely many steps in order to produce an output, but it may take arbitrarily many steps before halting. No time limitation is assumed.
3. Although the procedure may use only a finite amount of storage space during a successful computation, there is no bound on the amount of space that is used. It is assumed that additional storage space can be given to the procedure whenever the procedure asks for it.

To summarise, based on this view a function is computable if: (a) given an input from its domain, possibly relying on unbounded storage space, it can give the corresponding output by following a procedure (program, algorithm) that is formed by a finite number of exact unambiguous instructions; (b) it returns such output (halts) in a finite number of steps; and (c) if given an input which is not in its domain it either never halts or it gets stuck.

The field of computational complexity studies functions with prescribed bounds on the time and/or space allowed in a successful computation.

Computable sets and relations

A set A of natural numbers is called computable (synonyms: recursive, decidable) if there is a computable, total function f such that for any natural number n, f(n) = 1 if n is in A and f(n) = 0 if n is not in A.

A set of natural numbers is called computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that for each number n, f(n) is defined if and only if n is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The word enumerable is used because the following are equivalent for a nonempty subset B of the natural numbers:

• B is the domain of a computable function.
• B is the range of a total computable function. If B is infinite then the function can be assumed to be injective.

If a set B is the range of a function f then the function can be viewed as an enumeration of B, because the list f(0), f(1), ... will include every element of B.

Because each finitary relation on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions of computable relation and computably enumerable relation can be defined from their analogues for sets.

Formal languages

In computability theory in computer science, it is common to consider formal languages. An alphabet is an arbitrary set. A word on an alphabet is a finite sequence of symbols from the alphabet; the same symbol may be used more than once. For example, binary strings are exactly the words on the alphabet {0, 1} . A language is a subset of the collection of all words on a fixed alphabet. For example, the collection of all binary strings that contain exactly 3 ones is a language over the binary alphabet.

A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called computable (synonyms: recursive, decidable) if there is a computable function f such that for each word w over the alphabet, f(w) = 1 if the word is in the language and f(w) = 0 if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language.

A language is computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that f(w) is defined if and only if the word w is in the language. The term enumerable has the same etymology as in computably enumerable sets of natural numbers.

Examples

The following functions are computable:

• Each function with a finite domain; e.g., any finite sequence of natural numbers.
• Each constant function f : N^k → N, f(n₁,...n_k) := n.
• Addition f : N² → N, f(n₁,n₂) := n₁ + n₂
• The function which gives the list of prime factors of a number.
• The greatest common divisor of two numbers is a computable function.
• Bézout's identity, a linear Diophantine equation

If f and g are computable, then so are: f + g, f * g, ${\displaystyle f\circ g}$ if f is unary, max(f,g), min(f,g), arg max{y ≤ f(x)} and many more combinations.

The following examples illustrate that a function may be computable though it is not known which algorithm computes it.

• The function f such that f(n) = 1 if there is a sequence of at least n consecutive fives in the decimal expansion of π, and f(n) = 0 otherwise, is computable. (The function f is either the constant 1 function, which is computable, or else there is a k such that f(n) = 1 if n < k and f(n) = 0 if n ≥ k. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know which of those functions is f. Nevertheless, we know that the function f must be computable.)
• Each finite segment of an uncomputable sequence of natural numbers (such as the Busy Beaver function Σ) is computable. E.g., for each natural number n, there exists an algorithm that computes the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(n) — in contrast to the fact that there is no algorithm that computes the entire Σ-sequence, i.e. Σ(n) for all n. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of n, such a trivial algorithm exists (even though it may never be known or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(n).

Church–Turing thesis

The Church–Turing thesis states that any function computable from a procedure possessing the three properties listed above is a computable function. Because these three properties are not formally stated, the Church–Turing thesis cannot be proved. The following facts are often taken as evidence for the thesis:

• Many equivalent models of computation are known, and they all give the same definition of computable function (or a weaker version, in some instances).
• No stronger model of computation which is generally considered to be effectively calculable has been proposed.

The Church–Turing thesis is sometimes used in proofs to justify that a particular function is computable by giving a concrete description of a procedure for the computation. This is permitted because it is believed that all such uses of the thesis can be removed by the tedious process of writing a formal procedure for the function in some model of computation.

Provability

Given a function (or, similarly, a set), one may be interested not only if it is computable, but also whether this can be proven in a particular proof system (usually first order Peano arithmetic). A function that can be proven to be computable is called provably total.

The set of provably total functions is recursively enumerable: one can enumerate all the provably total functions by enumerating all their corresponding proofs, that prove their computability. This can be done by enumerating all the proofs of the proof system and ignoring irrelevant ones.

Relation to recursively defined functions

In a function defined by a recursive definition, each value is defined by a fixed first-order formula of other, previously defined values of the same function or other functions, which might be simply constants. A subset of these is the primitive recursive functions. Every such function is provably total: For such a k-ary function f, each value ${\displaystyle f(n_{1},n_{2}...n_{k})}$ can be computed by following the definition backwards, iteratively, and after finite number of iteration (as can be easily proven), a constant is reached.

The converse is not true, as not every provably total function is primitive recursive. Indeed, one can enumerate all the primitive recursive functions and define a function en such that for all n, m: en(n,m) = f_n(m), where f_n is the n-th primitive recursive function (for k-ary functions, this will be set to f_n(m,m...m)). Now, g(n) = en(n,n)+1 is provably total but not primitive recursive, by a diagonalization argument: had there been a j such that g = f_j, we would have got g(j) = en(j,j)+1 = f_j (j)+1= g(j)+1, a contradiction. (It should be noted that the Gödel numbers of all primitive recursive functions can be enumerated by a primitive recursive function, though the primitive recursive functions' values cannot).

One such function, which is provable total but not primitive recursive, is Ackermann function: since it is recursively defined, it is indeed easy to prove its computability (However, a similar diagonalization argument can also be built for all functions defined by recursive definition; thus, there are provable total functions that cannot be defined recursively^{[citation needed]}).

Total functions that are not provably total

In a sound proof system, every provably total function is indeed total, but the converse is not true: in every first-order proof system that is strong enough and sound (including Peano arithmetic), one can prove (in another proof system) the existence of total functions that cannot be proven total in the proof system.

If the total computable functions are enumerated via the Turing machines that produces them, then the above statement can be shown, if the proof system is sound, by a similar diagonalization argument to that used above, using the enumeration of provably total functions given earlier. One uses a Turing machine that enumerates the relevant proofs, and for every input n calls f_n(n) (where f_n is n-th function by this enumeration) by invoking the Turing machine that computes it according to the n-th proof. Such a Turing machine is guaranteed to halt if the proof system is sound.

Uncomputable functions and unsolvable problems

Every computable function has a finite procedure giving explicit, unambiguous instructions on how to compute it. Furthermore, this procedure has to be encoded in the finite alphabet used by the computational model, so there are only countably many computable functions. For example, functions may be encoded using a string of bits (the alphabet Σ = {0, 1}).
The real numbers are uncountable so most real numbers are not computable. See computable number. The set of finitary functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions are Busy beaver, Kolmogorov complexity, or any function that outputs the digits of a noncomputable number, such as Chaitin's constant.

Similarly, most subsets of the natural numbers are not computable. The halting problem was the first such set to be constructed. The Entscheidungsproblem, proposed by David Hilbert, asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed in the 1930s that this set of natural numbers is not computable. According to the Church–Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations.

Extensions of computability

Relative computability

The notion of computability of a function can be relativized to an arbitrary set of natural numbers A. A function f is defined to be computable in A (equivalently A-computable or computable relative to A) when it satisfies the definition of a computable function with modifications allowing access to A as an oracle. As with the concept of a computable function relative computability can be given equivalent definitions in many different models of computation. This is commonly accomplished by supplementing the model of computation with an additional primitive operation which asks whether a given integer is a member of A. We can also talk about f being computable in g by identifying g with its graph.

Higher recursion theory

Hyperarithmetical theory studies those sets that can be computed from a computable ordinal number of iterates of the Turing jump of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language of second order arithmetic and to some models of Hypercomputation. Even more general recursion theories have been studied, such as E-recursion theory in which any set can be used as an argument to an E-recursive function.

Hyper-computation

Although the Church–Turing thesis states that the computable functions include all functions with algorithms, it is possible to consider broader classes of functions that relax the requirements that algorithms must possess. The field of Hypercomputation studies models of computation that go beyond normal Turing computation.

Method to replace silicon with carbon nanotubes developed by IBM Research

Could work down to the 1.8 nanometer node in the future

October 2, 2015
Original link:  http://www.kurzweilai.net/method-to-replace-silicon-with-carbon-nanotubes-developed-by-ibm-research

Schematic of a set of molybdenum (M0) end-contacted

nanotube transistors (credit: Qing Cao et al./Science)

IBM Research has announced a “major engineering breakthrough” that could lead to carbon nanotubes replacing silicon transistors in future computing technologies.

As transistors shrink in size, electrical resistance increases within the contacts, which impedes performance. So IBM researchers invented a metallurgical process similar to microscopic welding that chemically binds the contact’s metal (molybdenum) atoms to the carbon atoms at the ends of nanotubes.

The new method promises to shrink transistor contacts without reducing performance of carbon-nanotube devices, opening a pathway to dramatically faster, smaller, and more powerful computer chips beyond the capabilities of traditional silicon semiconductors.

“This is the kind of breakthrough that we’re committed to making at IBM Research via our $3 billion investment over 5 years in research and development programs aimed a pushing the limits of chip technology,” said Dario Gil, VP, Science & Technology, IBM Research. “Our aim is to help IBM produce high-performance systems capable of handling the extreme demands of new data analytics and cognitive computing applications.”

The development was reported today in the October 2 issue of the journal Science.

Overcoming contact resistance

Schematic of carbon nanotube transistor contacts. Left: High-

resistance side-bonded contact, where the single-wall

nanotube (SWNT) (black tube) is partially covered by the

metal molybdenum (Mo) (purple dots). Right: low-resistance

end-bonded contact, where the SWNT is attached to the

 molybdenum electrode through carbide bonds, while the

carbon atoms (black dots) from the originally covered portion

of the SWNT uniformly diffuse out into the Mo electrode

(credit: Qing Cao et al./Science)

The new “end-bonded contact scheme” allows carbon-nanotube contacts to be shrunken down to below 10 nanometers without deteriorating performance. IBM says the scheme could overcome contact resistance challenges all the way to the 1.8 nanometer node and replace silicon with carbon nanotubes.

Silicon transistors have been made smaller year after year, but they are approaching a point of physical limitation. With Moore’s Law running out of steam, shrinking the size of the transistor — including the channels and contacts — without compromising performance has been a challenge for researchers for decades.

Single wall carbon nanotube (credit: IBM)

IBM has previously shown that carbon nanotube transistors can operate as excellent switches at channel dimensions of less than ten nanometers, which is less than half the size of today’s leading silicon technology. Electrons in carbon transistors can move more easily than in silicon-based devices and use less power.

Carbon nanotubes are also flexible and transparent, making them useful for flexible and stretchable electronics or sensors embedded in wearables.

IBM acknowledges that several major manufacturing challenges still stand in the way of commercial devices based on nanotube transistors.

Earlier this summer, IBM unveiled the first 7 nanometer node silicon test chip, pushing the limits of silicon technologies. 

References:

• Qing Cao, Shu-Jen Han, Jerry Tersoff, Aaron D. Franklin, Yu Zhu, Zhen Zhang, George S. Tulevski, Jianshi Tang, and Wilfried Haensch. End-bonded contacts for carbon nanotube transistors with low, size-independent resistance. Science 2 October 2015: 350 (6256), 68-72. [DOI:10.1126/science.aac8006]

Related:

• IBM Research Breakthrough Paves Way for Post-Silicon Future with Carbon Nanotube Electronics
• Carbon Nanotubes at 9 nm: A Q&A with IBM Research’s Shu-Jen Han

Structured programming

From Wikipedia, the free encyclopedia

 

Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making extensive use of the structured control flow constructs of selection (if/then/else) and repetition (while and for), block structures, and subroutines in contrast to using simple tests and jumps such as the go to statement, which can lead to "spaghetti code" that is potentially difficult to follow and maintain.

It emerged in the late 1950s with the appearance of the ALGOL 58 and ALGOL 60 programming languages,^[1] with the latter including support for block structures. Contributing factors to its popularity and widespread acceptance, at first in academia and later among practitioners, include the discovery of what is now known as the structured program theorem in 1966,^[2] and the publication of the influential "Go To Statement Considered Harmful" open letter in 1968 by Dutch computer scientist Edsger W. Dijkstra, who coined the term "structured programming".^[3]

Structured programming is most frequently used with deviations that allow for clearer programs in some particular cases, such as when exception handling has to be performed.

Elements

Control structures

Following the structured program theorem, all programs are seen as composed of control structures:

• "Sequence"; ordered statements or subroutines executed in sequence.
• "Selection"; one or a number of statements is executed depending on the state of the program. This is usually expressed with keywords such as if..then..else..endif.
• "Iteration"; a statement or block is executed until the program reaches a certain state, or operations have been applied to every element of a collection. This is usually expressed with keywords such as while, repeat, for or do..until. Often it is recommended that each loop should only have one entry point (and in the original structural programming, also only one exit point, and a few languages enforce this).
• "Recursion"; a statement is executed by repeatedly calling itself until termination conditions are met. While similar in practice to iterative loops, recursive loops may be more computationally efficient, and are implemented differently as a cascading stack.

Graphical representation of the three basic patterns — 

sequence, selection, and repetition — using NS diagrams (blue)

and flow charts (green).

Subroutines

Subroutines; callable units such as procedures, functions, methods, or subprograms are used to allow a sequence to be referred to by a single statement.

Blocks

Blocks are used to enable groups of statements to be treated as if they were one statement. Block-structured languages have a syntax for enclosing structures in some formal way, such as an if-statement bracketed by if..fi as in ALGOL 68, or a code section bracketed by BEGIN..END, as in PL/I and Pascal, whitespace indentation as in Python - or the curly braces {...} of C and many later languages.

Structured programming languages

It is possible to do structured programming in any programming language, though it is preferable to use something like a procedural programming language. Some of the languages initially used for structured programming include: ALGOL, Pascal, PL/I and Ada, but most new procedural programming languages since that time have included features to encourage structured programming, and sometimes deliberately left out features – notably GOTO – in an effort to make unstructured programming more difficult. Structured programming (sometimes known as modular programming) enforces a logical structure on the program being written to make it more efficient and easier to understand and modify.

History

Theoretical foundation

The structured program theorem provides the theoretical basis of structured programming. It states that three ways of combining programs—sequencing, selection, and iteration—are sufficient to express any computable function. This observation did not originate with the structured programming movement; these structures are sufficient to describe the instruction cycle of a central processing unit, as well as the operation of a Turing machine. Therefore, a processor is always executing a "structured program" in this sense, even if the instructions it reads from memory are not part of a structured program. However, authors usually credit the result to a 1966 paper by Böhm and Jacopini, possibly because Dijkstra cited this paper himself.^[4] The structured program theorem does not address how to write and analyze a usefully structured program. These issues were addressed during the late 1960s and early 1970s, with major contributions by Dijkstra, Robert W. Floyd, Tony Hoare, Ole-Johan Dahl, and David Gries.

Debate

P. J. Plauger, an early adopter of structured programming, described his reaction to the structured program theorem:

Us converts waved this interesting bit of news under the noses of the unreconstructed assembly-language programmers who kept trotting forth twisty bits of logic and saying, 'I betcha can't structure this.' Neither the proof by Böhm and Jacopini nor our repeated successes at writing structured code brought them around one day sooner than they were ready to convince themselves.^[5]

Donald Knuth accepted the principle that programs must be written with provability in mind, but he disagreed (and still disagrees^{[citation needed]}) with abolishing the GOTO statement. In his 1974 paper, "Structured Programming with Goto Statements",^[6] he gave examples where he believed that a direct jump leads to clearer and more efficient code without sacrificing provability. Knuth proposed a looser structural constraint: It should be possible to draw a program's flow chart with all forward branches on the left, all backward branches on the right, and no branches crossing each other. Many of those knowledgeable in compilers and graph theory have advocated allowing only reducible flow graphs^{[when defined as?]}.^[who?]

Structured programming theorists gained a major ally in the 1970s after IBM researcher Harlan Mills applied his interpretation of structured programming theory to the development of an indexing system for The New York Times research file. The project was a great engineering success, and managers at other companies cited it in support of adopting structured programming, although Dijkstra criticized the ways that Mills's interpretation differed from the published work.^{[citation needed]}

As late as 1987 it was still possible to raise the question of structured programming in a computer science journal. Frank Rubin did so in that year with an open letter titled ""GOTO considered harmful" considered harmful".^[7] Numerous objections followed, including a response from Dijkstra that sharply criticized both Rubin and the concessions other writers made when responding to him.

Outcome

By the end of the 20th century nearly all computer scientists were convinced that it is useful to learn and apply the concepts of structured programming. High-level programming languages that originally lacked programming structures, such as FORTRAN, COBOL, and BASIC, now have them.

Common deviations

While goto has now largely been replaced by the structured constructs of selection (if/then/else) and repetition (while and for), few languages are purely structured. The most common deviation, found in many languages, is the use of a return statement for early exit from a subroutine. This results in multiple exit points, instead of the single exit point required by structured programming. There are other constructions to handle cases that are awkward in purely structured programming.

Early exit

The most common deviation from structured programming is early exit from a function or loop. At the level of functions, this is a return statement. At the level of loops, this is a break statement (terminate the loop) or continue statement (terminate the current iteration, proceed with next iteration). In structured programming, these can be replicated by adding additional branches or tests, but for returns from nested code this can add significant complexity. C is an early and prominent example of these constructs. Some newer languages also have "labeled breaks", which allow breaking out of more than just the innermost loop. Exceptions also allow early exit, but have further consequences, and thus are treated below.

Multiple exits can arise for a variety of reasons, most often either that the subroutine has no more work to do (if returning a value, it has completed the calculation), or has encountered "exceptional" circumstances that prevent it from continuing, hence needing exception handling.

The most common problem in early exit is that cleanup or final statements are not executed – for example, allocated memory is not deallocated, or open files are not closed, causing memory leaks or resource leaks. These must be done at each return site, which is brittle and can easily result in bugs. For instance, in later development, a return statement could be overlooked by a developer, and an action which should be performed at the end of a subroutine (e.g., a trace statement) might not be performed in all cases. Languages without a return statement, such as standard Pascal, do not have this problem.

Most modern languages provide language-level support to prevent such leaks;^[8] see detailed discussion at resource management. Most commonly this is done via unwind protection, which ensures that certain code is guaranteed to be run when execution exits a block; this is a structured alternative to having a cleanup block and a goto. This is most often known as try...finally, and considered a part of exception handling. Various techniques exist to encapsulate resource management. An alternative approach, found primarily in C++, is Resource Acquisition Is Initialization, which uses normal stack unwinding (variable deallocation) at function exit to call destructors on local variables to deallocate resources.

Kent Beck, Martin Fowler and co-authors have argued in their refactoring books that nested conditionals may be harder to understand than a certain type of flatter structure using multiple exits predicated by guard clauses. Their 2009 book flatly states that "one exit point is really not a useful rule. Clarity is the key principle: If the method is clearer with one exit point, use one exit point; otherwise don’t". They offer a cookbook solution for transforming a function consisting only of nested conditionals into a sequence of guarded return (or throw) statements, followed by a single unguarded block, which is intended to contain the code for the common case, while the guarded statements are supposed to deal with the less common ones (or with errors).^[9] Herb Sutter and Andrei Alexandrescu also argue in their 2004 C++ tips book that the single-exit point is an obsolete requirement.^[10]

In his 2004 textbook, David Watt writes that "single-entry multi-exit control flows are often desirable". Using Tennent's framework notion of sequencer, Watt uniformly describes the control flow constructs found in contemporary programming languages and attempts to explain why certain types of sequencers are preferable to others in the context of multi-exit control flows. Watt writes that unrestricted gotos (jump sequencers) are bad because the destination of the jump is not self-explanatory to the reader of a program until the reader finds and examines the actual label or address that is the target of the jump. In contrast, Watt argues that the conceptual intent of a return sequencer is clear from its own context, without having to examine its destination. Watt writes that a class of sequencers known as escape sequencers, defined as a "sequencer that terminates execution of a textually enclosing command or procedure", encompasses both breaks from loops (including multi-level breaks) and return statements. Watt also notes that while jump sequencers (gotos) have been somewhat restricted in languages like C, where the target must be an inside the local block or an encompassing outer block, that restriction alone is not sufficient to make the intent of gotos in C self-describing and so they can still produce "spaghetti code". Watt also examines how exception sequencers differ from escape and jump sequencers; this is explained in the next section of this article.^[11]

In contrast to the above, Bertrand Meyer wrote in his 2009 textbook that instructions like break and continue "are just the old goto in sheep's clothing" and strongly advised against their use.^[12]

Exception handling

Based on the coding error from the Ariane 501 disaster, software developer Jim Bonang argues that any exceptions thrown from a function violate the single-exit paradigm, and proposes that all inter-procedural exceptions should be forbidden. In C++ syntax, this is done by declaring all function signatures as noexcept (since C++11) or throw().^[13] Bonang proposes that all single-exit conforming C++ should be written along the lines of:

bool myCheck1() throw()
{
  bool success = false;

  try 
  {
    // do something that may throw exceptions
    if(myCheck2() == false) 
    {
        throw SomeInternalException();
    }

    // other code similar to the above
    success = true;
  }

  catch(...)
  {
      // all exceptions caught and logged
  }

  return success;
}

Peter Ritchie also notes that, in principle, even a single throw right before the return in a function constitutes a violation of the single-exit principle, but argues that Dijkstra's rules were written in a time before exception handling became a paradigm in programming languages, so he proposes to allow any number of throw points in addition to a single return point. He notes that solutions which wrap exceptions for the sake of creating a single-exit have higher nesting depth and thus are more difficult to comprehend, and even accuses those who propose to apply such solutions to programming languages which support exceptions of engaging in cargo cult thinking.^[14]

David Watt also analyzes exception handling in the framework of sequencers (introduced in this article in the previous section on early exits.) Watt notes that an abnormal situation (generally exemplified with arithmetic overflows or input/output failures like file not found) is a kind of error that "is detected in some low-level program unit, but [for which] a handler is more naturally located in a high-level program unit". For example, a program might contain several calls to read files, but the action to perform when a file is not found depends on the meaning (purpose) of the file in question to the program and thus a handling routine for this abnormal situation cannot be located in low-level system code. Watts further notes that introducing status flags testing in the caller, as single-exit structured programming or even (multi-exit) return sequencers would entail, results in a situation where "the application code tends to get cluttered by tests of status flags" and that "the programmer might forgetfully or lazily omit to test a status flag. In fact, abnormal situations represented by status flags are by default ignored!" He notes that in contrast to status flags testing, exceptions have the opposite default behavior, causing the program to terminate unless the programmer explicitly deals with the exception in some way, possibly by adding code to willfully ignore it. Based on these arguments, Watt concludes that jump sequencers or escape sequencers (discussed in the previous section) aren't as suitable as a dedicated exception sequencer with the semantics discussed above.^[15]

The textbook by Louden and Lambert emphasizes that exception handling differs from structured programming constructs like while loops because the transfer of control "is set up at a different point in the program than that where the actual transfer takes place. At the point where the transfer actually occurs, there may be no syntactic indication that control will in fact be transferred."^[16] Computer science professor Arvind Kumar Bansal also notes that in languages which implement exception handling, even control structures like for, which have the single-exit property in absence of exceptions, no longer have it in presence of exceptions, because an exception can prematurely cause an early exit in any part of the control structure; for instance if init() throws an exception in for (init(); check(); increm()), then the usual exit point after check() is not reached.^[17] Citing multiple prior studies by others (1999-2004) and their own results, Westley Weimer and George Necula wrote that a significant problem with exceptions is that they "create hidden control-flow paths that are difficult for programmers to reason about".^[18]:8:27

The necessity to limit code to single-exit points appears in some contemporary programming environments focused on parallel computing, such as OpenMP. The various parallel constructs from OpenMP, like parallel do, do not allow early exits from inside to the outside of the parallel construct; this restriction includes all manner of exits, from break to C++ exceptions, but all of these are permitted inside the parallel construct if the jump target is also inside it.^[19]

Multiple entry

More rarely, subprograms allow multiple entry. This is most commonly only re-entry into a coroutine (or generator/semicoroutine), where a subprogram yields control (and possibly a value), but can then be resumed where it left off. There are a number of common uses of such programming, notably for streams (particularly input/output), state machines, and concurrency. From a code execution point of view, yielding from a coroutine is closer to structured programming than returning from a subroutine, as the subprogram has not actually terminated, and will continue when called again – it is not an early exit. However, coroutines mean that multiple subprograms have execution state – rather than a single call stack of subroutines – and thus introduce a different form of complexity.
It is very rare for subprograms to allow entry to an arbitrary position in the subprogram, as in this case the program state (such as variable values) is uninitialized or ambiguous, and this is very similar to a goto.

State machines

Some programs, particularly parsers and communications protocols, have a number of states that follow each other in a way that is not easily reduced to the basic structures, and some programmers implement the state-changes with a jump to the new state. This type of state-switching is often used in the Linux kernel.^{[citation needed]}

However, it is possible to structure these systems by making each state-change a separate subprogram and using a variable to indicate the active state (see trampoline). Alternatively, these can be implemented via coroutines, which dispense with the trampoline.

Overcoming transistor miniaturization limits due to ‘quantum tunneling’

Breakthrough could jumpstart further miniaturization of transistors, possibly extending Moore's law

June 7, 2018
Original link:  http://www.kurzweilai.net/overcoming-transistor-miniaturization-limits-due-to-quantum-tunneling

An illustration of a single-molecule device that blocks leakage current in a transistor (yellow: gold transistor electrodes) (credit: Haixing Li/Columbia Engineering)

A team of researchers at Columbia Engineering and associates* have synthesized a molecule that could overcome a major physical limit to miniaturizing computer transistors at the nanometer scale (under about 3 nanometers) — caused by “leakage current.”

Leakage current between two metal transistor electrodes results when the gap between the electrodes narrows to the point that electrons are no longer contained by their barriers — a phenomenon known as quantum tunneling.

The researchers synthesized the first molecule** capable of insulating (preventing electron flow) at the nanometer scale more effectively than a vacuum barrier (the traditional approach). The molecule bridges the nanometer gap between two metal electrodes.

Constructive interference (left) between two waves increases the resulting wave; destructive interference (right) decreases the resulting wave. (credit: Wikipedia)

The silicon-based molecule design uses “destructive quantum interference,” which occurs when the peaks and valleys of two waves are placed exactly out of phase, annulling oscillation.

“We’ve reached the point where it’s critical for researchers to develop creative solutions for redesigning insulators. Our molecular strategy represents a new design principle for classic devices, with the potential to support continued miniaturization in the near term,” said Columbia Engineering physicist Latha Venkataraman, Ph.D.

The research bucks the trend of most research in transistor miniaturization, which aims to create highly conducting contact electrodes, typically using carbon nanotubes (see “Method to replace silicon with carbon nanotubes developed by IBM Research”).

* Other researchers on the team were from Columbia University Department of Chemistry, Shanghai Normal University, and the University of Copenhagen.

** The molecule is bicyclo[2.2.2]octasilane.