Proving uncountability without diagonalization

In this post, I propose a proof of the uncountability of the set of real numbers without using the famous diagonalization method of Georg Cantor. My proof is based on the Church-Turing thesis which states that any computable operation may be computed or simulated by a Turing Machine. So, if a set of mathematical objects is countable a counting operation may be performed and there is a Turing Machine that may compute it.

Definition. Let S be an ordered set of discrete objects. If S is countable then there is Turing Machine M which on input of the descriptions of objects a and b it outputs c which is a representation of the number of elements in S between objects a and b.

If we may count the elements between a and b (or else the distance of a and b in S) then we may count the whole set, as a and b may be any objects. This definition avoids a direct connection of the set N of natural numbers to S, so it differs from diagonalization, yet as I show below it reaches the same conclusions on natural, rational and real numbers. Output c has to be a number and not the symbol of infinity or anything similar, otherwise we cannot consider it as a counting result. First let’s test this definition on natural and rational numbers.

Theorem 1. Set N of natural numbers and set Q or rational numbers are countable.

Proof for N. Set N may be defined as an ordered set of linear structure. For every i we place in the i-th place of N number i. Let a and b be the representations of two natural numbers where a represents a smaller value than b and M a TM that computes their distance. In order to make the presentation more simple and intuitive and without loss of generality, let M be a 2-tape machine and a, b and c be represented in unary numeral system. Then we print a in tape-1 and b in tape-2. For any “1” printed in tape-1 M erases one “1” that is printed in tape-2. Finally a representation of c is left in tape-2 and this is the output.

For instance, on a = 8 and b = 13 we print
tape-1 : #11111111######
tape-2 : #1111111111111#
After running the configuration of M we get
tape-1 : #11111111######
tape-2 : #11111#########

Proof for Q. Let’s first define Q as an ordered set. It is known that Q may be defined as the Cartesian product of sets X and Y, where X and Y are equal to N / {0}. For every ordered pair (x, y) of the product there is corresponding number q which is in Q and stands that q = y / x. Using this definition we may create an ordered set of linear structure equivalent to Q.

Set Q may be structured as an ordered set of subsets. Initially we place numbers “0” and “1 /1”, then for every i > 2 we place in the i-th place of the set the subset of Q that for all its elements stands x+y=i. By placing in ascending order the elements within each subset we create an ordered set of linear structure with all the elements of Q. On this procedure we end up with a representation of Q that is commonly used in literature.

On input of the descriptions of a and b, TM M using the above procedure creates the ordered subset of Q that contains a and b and then computes their distance by simply counting the elements between them one by one.

The ordered set of linear structure that is subset of Q and contains a and b is computable as it may be constructed algorithmically as shown above and is finite as I will show next.

Let a=y1/x1 and b=y2/x2, then between a and b there is a finite number of subsets d= (x2+y2)-(x1+y1). For each subset stands that i=x+y and is finite as there is a finite number of combinations that may generate i given that i, x, y belong in N.

Cartesian product

1/1   1/2   1/3   1/4 ……
2/1   2/2   2/3   2/4 ……
3/1   3/2   3/3   3/4 ……
4/1   4/2   4/3   4/4 ……
………………………..

Order of elements

 1       2       4       7  ……
 3       5       8      11 ……
 6       9      12     14 ……
10     13     15     16 ……
………………………...


Q as set of subsets

(0), (1/1), (1/2, 2/1), (1/3, 2/2, 3/1), (1/4, 2/3, 3/2, 4/1), (… 2/4, 3/3, 4/2 …), (… 3/4, 4/3 …), (… 4/4 …)


Q as an ordered set of linear structure

0, 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, …, 2/4, 3/3, 4/2, …, 3/4, 4/3, …, 4/4 …


Theorem 2. The set R of real numbers is uncountable.

Proof. It is known that there is no algorithmic procedure which may produce the numbers in R. That is because most of numbers in R are uncomputable. 

Let's consider a description d for the numbers in R so that they may be represented in TM M. If there is procedure implemented in M that structures R as an ordered set then M computes uncomputable numbers which is a contradiction. As a result R may not be structured as an ordered set and is not countable by M.

System security as a computational problem

In this post I talk about system security and I examine it as a computational problem. The motivation of thinking about this came from a very interesting post by Dick Lipton and Ken Regan that was published on their blog a few days ago.
The problem of developing a secure system regards the development of a system that will maintain a set of information F which will only be accessible by authorised users. As a result, any unauthorised user will be excluded from accessing F. A good way to study the system is to model it using Turing thesis.
Any user  has to provide some input like username and password in order to get clearance and usually F is represented by some text or binary information, so let's define F as a set of strings and w as a string which is the user input. Also let A be a Turing Machine that simulates the system we have developed and we consider it secure.
Some systems in order to identify authorised users demand extensive interaction which results that users have to fill questionnaires and forms. Without loss of generality, we may enclose all the user input in w also the acceptance or rejection of it by the system may be modeled efficiently by the operation of A. On this assumption, A will accept a valid w and output F or reject input from not authorized users and output "NO".
Let S be a set of strings so that if A decides that input w belongs to S then the user is considered as authorized and F is outputted. There are two cases where this model does not work as expected.
Case1. There is string e that does not belong to S and on input in A, it outputs F. So an intruder may use e in order to gain access to F without knowing w.
Case2. String w may be discovered algorithmically by unauthorized users.

Some explanation on these cases.
In case1 I model the cases of the real world where A is hacked. The intruder does not input the identification of some authorized user in order to access F, so user input does not belong to S. The intruder inputs a string that will cause A to get undesired behavior and this will result the output of F. In real world, sometimes the intruders exploit security holes and send data to the systems (like macros, telnet commands or Trojans) that cause such undesired behavior.

Case2 refers to the complexity of w and how easily it can be guessed.

Intentionally I leave out the cases where w has been stolen from its owner with techniques likes phishing or similar; this seems to be more of a social than a computational problem.

The computability of security and why hacking is easier that defending

The following language describes Case1 as a computational problem.
SECURITY1 = {A, S, F, e | There is string e that does not belong to set S, TM A outputs F and halts on input e.}

Theorem. Problem SECURITY1 is recognizable and undecidable.

Proof. SECURITY1 is recognizable. We input in A string e that does not belong to S and we get F. If SECURITY1 is also decidable then for any input s that does not belong to S, we may decide whether machine A halts and outputs F or “NO”. As A can be any TM and s any string, these assumptions stand only if the halting problem is decidable and this results a contradiction.

Although both the developer of A and an intruder face the same problem, as they both have to solve one instance of SECURITY1 in order to build or hack A. Yet, the job of the intruder is easier than the job of the developer. The intruder has to solve the recognizable side of the problem while the defender has to approach the undecidable side of it.
In other words, if you try to intrude A you build a process described by string e and once you input it to A you can find out if it works. If you are a defender you can never be sure that the system that you build will be strong enough to resist attacks. Building A is a far more complex task than discovering e and that is why you see systems that are developed by experienced developing teams to have been hacked by some technology enthusiast teenager.

 

About Case 2

Case2 refers to the complexity of w or else to the complexity of the procedure of entering user identification data. There is no point on examining the computability of such processes as most of them are in theory computable. For instance, when a user has to enter a 4 digit PIN in a system the number of possible PINs that may be entered is bounded and in theory it is computable. If we enter the restriction that the user has only three attempts to enter the correct PIN then it gets difficult for an intruder to guess the PIN.
The proposed approach by Lipton and Regan actually increases the complexity of the procedure of identification. It gets harder for an intruder to guess w which may be subject to frequent changes if the questions asked by the system change frequently.



The image on this post is freely available under Creative Commons License. Check the source for the original image and many more.

Building interaction between Android and Javascript

In this post I present methods on how to build interaction between Javascript content in a webpage and the Java code of an Android application. When building an application with web content (build-in or loaded from network) there is always the issue on how it will communicate with the rest of the application. The interaction has to be two-way. The web content probably hosted in a webview has to be able to affect the rest of the application based on user interaction and Android must be able to change the web content. There is not a unified way to build a two-way bridge between the two interfaces, Javascript and Android have to bind with each other using separate processes.
Let’s suppose that you are building an app with one activity named Activity1that hosts a webview which opens the local file HTML1.html (the examples that follow also work when files are somewhere in a network and not local). In Activity1 there are some String variables v1, v2, v3. Corresponding variables with capital letter names are defined in some javascript code enclosed in HTML1.

At first the variables and the webview in Activity1 have to be declared properly and Javascript support has to be enabled.

Code to place in Activity1

String v1, v2, v3;
WebView webView;

//In the onCreate method add
webView = (WebView) findViewById(R.id.webview);
WebSettings webSettings = webView.getSettings();
webSettings.setJavaScriptEnabled(true);

Variable declaration in a script in HTML1.html

var V1=”Value of v1”;
var V2=”Value of v2”;
var V3=”Value of v3”;

Updating variables in Javascript

I present two techniques for updating the variables in Javascript. In the first the necessary code will be loaded in Javascript before HTML1 will be loaded in webview and this is the main advantage of this technique.
In order to change the Javascript code that runs in webview, I create programmatically a file that contains the code I care to run and then I insert it to HTML1. As a technique may not be so elegant, but it has certain advantages. Another advantage of this technique is that the preservation of the information that regards the variables does not depend on the life circle of Activity1. So, the file may be store while running Activity1 and other activities that will open in the future may read it and update their variables.

In Activity1

At first the path of the file that will be dynamically created has to be defined. A good choice is to place it in the files directory of the application. The directory path can be accessed using the getFilesDir() method. Then it is only necessary to add the code that creates the file.

File jsfile = new File(getFilesDir() + File.separator+"new.js");

public void filecreator(){

v1="new value1";
v2="new value1";
v3="new value1";

BufferedWriter buffer = null;       
    try{               
        buffer=new BufferedWriter(new FileWriter(jsfile));
        buffer.write("V1="+v1+";");
        buffer.newLine();
        buffer.write("V2="+v2+";");
        buffer.newLine();
        buffer.write("V3="+v3+";");
        buffer.newLine();
        buffer.flush();       
        buffer.close();
}
    catch (IOException ex){
        String ioerror=ex.toString();
    }
}

Then simply call the method while running Activity1.

In HTML1.html

Insert the newly created file in the body or the head of the html code.

<script src="jsfile.js" type="text/javascript"></script>

If both HTML1.html and jsfile.js are in the same directory then it is not necessary to determine the full path of the file and the code above is enough.

Another more elegant technique is to load the script using method
webView.loadUrl(("javascript: /*some code*/")
In this case you only add the following code in Activity1 and don’t make any changes in HTML1.

webView01.loadUrl("javascript: V1=’new value1’; V2=’new value1’; V3=’new value1’");

The above script will be executed after HTML1 has been fully loaded in webview. You have to be careful on this, as executing the script before loading the html file might lead to undesired behavior.

Updating Android variables from Javascript

Let’s see how running Javascript can affect the variables of Activity1 by modifying the example in Android Developers site (link).

In Activity1 

Add a WebAppInterface class. The methods of the class must overidde JavascriptInterface in order to work with the latest versions of Android.

public class WebAppInterface {
   Context mContext;

   WebAppInterface(Context c) {
       mContext = c;
   }
       
   @JavascriptInterface
   public void updatevariables(String V1, String V2, String V3) {
        v1=V1;

        v2=V2;
        v3=V3;
   }

}

In this implementation, the method updatevariables is called from Javascript that runs in the webview. The values that should be set in the variables v1, v2 , v3 are passed to the formal parameters of the method (String V1, String V2, String V3) and the code that follows updates the variables in Activity1.

Code to place in HTML1.html

function updatevariables (V1, V2, V3) {
    Android. updatevariables (V1, V2, V3);
}

In some part of the script in HTML1.html call the function updatevariables and the values of v1, v2, v3 will be updated.

John Forbes Nash (1928 – 2015)

Alicia Nash (1933 – 2015)

 

. RIP

On the computability of causal inference

Causation (or else causality) refers to the cause-effect relation that may exist between two events or phenomena. The causal inference problem regards the determination of causation between events.
Let’s consider the case where there is an interaction between two events which is not affected by any other factor or event. The two events are observable and measurable and for each one we may record a set of data that describes it. Then the causal inference problem is equivalent to the existence of a computable relationship between the two data sets that describe the events.
As I show next, the general case of the problem of causal inference even with the above assumptions is undecidable and this has important implications in science. The undecidability of a problem means that there are some instances of it that may not be proven true or false, while other instances may be decidable.

Let’s formulate the general case of the causal inference problem as a decision problem. Let A and B be two sets of data.

CAUSAL = {A, B | There is computable function f(A) = B}
It is enough to use the formulation of CAUSAL in order to describe causal inference problem. If there is a cause-effect relationship between A and B then there is function f so that f(A) = B and if CAUSAL was proven decidable then f would be computable in any case.
Let me restrict this discussion in data sets and phenomena that their measurements are as accurate as it is demanded. The meaning of this assumption is that the data of the problem is not affected by factors that would make their computation inaccurate like the principle of uncertainty. Also, this implies that the elements of both sets are computable. The earlier assumption that the two events interact and are not affected by any other factor simplifies the definition of the problem, as it implies that if there is computable function f between A and B this describes a cause-effect relationship and it is not coincidental.
In the general case the problem is not trivial as A and B may be the products of complex or even chaotic systems and natural procedures. Here the term “trivial” is used in the sense of mathematical logic.

Theorem. The causal inference problem is logically and computationally undecidable.

Proof of logical undecidability. If the problem is decidable then we may construct a system using which we may prove every instance of the problem. We may encode using Gödel numbering and arithmetic each element a and b of A and B in a formal system of logic P so that for every sentence S of the form a -> b, S or -S is provable so that eventually the sentences A -> B or -A -> B will be provable. The problem is complex so P will be sufficiently strong.
This consideration results a contradiction, as proven by Kurt Gödel (Gödel, 1931) in such a system there are true sentences that are not provable. The problem is logically undecidable.

Proof of computable undecidability. If CAUSAL is decidable, then there is Turing Machine M which on input of a string e that contains the descriptions of A and B always halts and outputs “YES” or ”NO”.
As the problem is assumed decidable and M is computable, we may construct Turing Machine N that when inputting string w that contains the description of M and e verifies that M decides e; N accepts w in any case. There are no restrictions in the nature of A and B or their encoding and representation in e, hence w can be any string. Also there are no restrictions in the description of M and N, they can be any Turing Machines.
As a result, the language ATM = {N, w | N is a Turing Machine and accepts w} is decidable. This is a contradiction. As it is known from literature that ATM is undecidable; see (Sipser 2006, p.179). Hence CAUSAL is also computationally undecidable.
Another way to reason about the computational undecidability of CAUSAL is to consider Turing Machine N that simulates the phenomenon described by A. We input in N a string w that describes set A, then N produces a string that describes set B and then halts. If CAUSAL was decidable then N would be computable. The string that describes A may be any string as there is no restriction to the event that A describes; so N halts on any given input. Also N may be any Turing Machine.
Still these assumptions lead to the same contradiction; if CAUSAL was computable so would be language ATM.

Laplace’s demon

The undecidability of causal inference has an effect on the famous idea of the demon of Laplace.

“We may regard the present state of the universe as the effect of its past and the cause of its future. An intellect which at a certain moment would know all forces that set nature in motion, and all positions of all items of which nature is composed, if this intellect were also vast enough to submit these data to analysis, it would embrace in a single formula the movements of the greatest bodies of the universe and those of the tiniest atom; for such an intellect nothing would be uncertain and the future just like the past would be present before its eyes.”

Pierre Simon Laplace, A Philosophical Essay on Probabilities 1820
source: Wikipedia, also in (Laplace, 1951, p.4)

The intellect that described in the text was later named “Laplace’s demon”. There has been criticism against this idea and some published proofs against it. The proofs presented above are also against this idea. Such an intellect or demon should be able to decide CAUSAL which is undecidable.

The extend of undecidability

In every undecidable problem there are some instances that are decidable and some that are not. To put it another way, each undecidable problem is undecidable to some extent. Logic and the theory of computation have not been able to determine this extent for every problem. For some problems like the halting problem this extent seems large; only very simple instances of the halting problem seem computable.
In causal inference, things must be different. Science and especially Artificial Intelligence has managed to build successful methods in computing quite a lot of instances of the problem. The importance in these methods is that they may be applied in the analysis of real world phenomena. In my opinion, some of the reasons of successful predictions in real world phenomena are bounded inputs, relaxation, approximation and strong hypotheses.

Bounded inputs. Real world phenomena usually don’t take arbitrary large or small values. The possible values in the parameters of a phenomenon are bounded. This results that the problem range is reduced making computations easier.
Relaxation. Relaxing some parameters in the definition of a problem might lead to the computation of an easier problem. In some cases the conclusions from the definition of the easier problem are as valuable as the solution of the initial problem is.
Approximation. It is quite often that the solutions of hard problems may be approximated, which is valuable when precision is not very important.
Strong hypotheses. Sometimes scientists have strong evidence and strong intuition about a certain universal truth that cannot be proven or it is at least very difficult to be proved. In these cases researcher state it as a hypothesis and accept it as an unproven true fact and they may work on it overriding the obstacle of finding a solid proof for it. The biggest part of this post is based on such a hypothesis; it is the Church - Turing Thesis (Turing, 1936).

References

Gödel, Kurt, 1931. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. and On formally undecidable propositions of Principia Mathematica and related systems I in Solomon Feferman, ed., 1986. Kurt Gödel Collected works. Vol. I. Oxford University Press, pp 144-195.

Laplace, Pierre Simon, 1951. A Philosophical Essay on Probabilities, translated into English from the original French 6th ed. by Truscott,F.W. and Emory,F.L., Dover Publications (New York, 1951)

Sipser, Michael, 2006. Introduction to the Theory of Computation, Second Edition. Thomson Course Technology, USA.

Turing, Alan M., 1936. On Computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society. 42, 230–265.