Category Basic Concepts

Basic Concepts 9 – Productive Sets and Productive Functions

In a previous article, I have sketched a proof that shows that the set of computable total functions (as well as the sets of programs calculating them, and of the Gödel numbers of such programs) is not enumerable. I want to look into this matter in more detail here. All of these sets are not enumerable, […]

Basic Concepts 8 – Formal Theories and Formal Systems

Occasionally in this series of articles, and in this blog, I have been writing about “formal theories”. I don’t intend to introduce a formal definition of what a formal theory is here. I only want to provide an intuitive understanding. So this article is not meant for mathematicians or logicians or computer scientists, who might […]

Basic concepts 7 – Formalizations of Computability

In order to turn the intuitive concepts discussed in the previous article into exact concepts, one would have to define exactly what a program is. Different mathematicians (including Alan Turing, Alonzo Church, Stephen Cole Kleene and others) have come up with different formalisms in order to define exactly what a computable function is and thus […]

Basic Concepts 6 – Computability, Decidability and Enumerability

In the first article of this series, we encountered the concept of a function. In the previous article, we have gained a first, intuitive understanding of programs. We can now define a few basic concepts. A rigorous and exact definition would require that we define the concept of a program more exactly, but it is […]

Basic Concepts 5 – Computers and Programs

In this article, we are starting to look at programs and computers. This is a complex matter and I will only touch a few aspects of this topic here. We can think of a computer as a machine that processes data. We put in input data and it produces output data (I am only looking […]

Basic Concepts 4  – Gödel Numbers

It is possible to define a mapping from arbitrary data into natural numbers and vice versa. There are many ways in which this could be done and I am going to explain just one here. You might ask what this is good for. That is a good question. At the present moment I can only […]

Basic Concepts 3 – Data and its Binary Representation

If you are reading this article, it is likely that you own or have access to a computer. Devices like laptops, tablets and smartphones, but also internet servers are all computers. Computers might contain different types of data, like texts, pictures, sound files, films, web pages, spread sheets, etc. For each type of data, there […]