A machine told you to fall in love and you fell for it

by Edward De Brouwer and Giulia Lazzara

The Halting Problem

(Informal) Statement

Given an input, any machine either processes that input in a finite amount of time (it halts), or runs forever in an infinite loop. The halting problem asks whether it is possible to create a machine that, given any other machine and its input, can determine whether that machine will eventually halt, or not.

$$♥$$

(Informal) Proof

Let $M$ be the set of all possible machines, and $X$ the space of program inputs.

$$\exists m \in M : \forall n \in M, \forall x \in X,$$ $$m(n, x) = n(x)$$

Let $k \in M$ with $ k := k(x) = \neg m(k, x), \forall x \in X $.

Now,

$$m(k, x) = k(x)$$ $$= \neg m(k, x)$$

$$\bot$$

G looks at E. His face hides behind the plastic-wrapped menu of the diner where they have breakfast together every Sunday morning. His venetian blond hair is standing straight up as if held still by an invisible pillow. He refuses to comb it, but now she’s glad he doesn’t. She studies how the light flows in from the window to sit on his cheek and shoulder. She would like for this moment to never end. Perhaps he knows, and he’s taking his time with the menu even though he’s going to get what he always gets: blueberry waffles with coffee and an orange juice, no whipped cream please. She’s also getting her usual sausage pancakes with maple syrup, but neither of them is thinking about their breakfast options. It is one of the few diners in the city that still puts menus on the tables and nobody really uses them anymore. As everyone has a prefixed diet that assures their optimal nutrition, the menus are there to serve a feeling of nostalgia of a different time in history. Like the extra bottles of condiments next to them, they are purely aesthetic. But they don’t want to be. Not anymore. Today they will choose, and it will change everything. Or maybe nothing, they cannot know for sure, but they have anticipated this moment for so long now. An unknown cocktail of excitement and fear fills the air between them for they aren’t sure of what is going to happen next. Every possible outcome is playing out again in her head, on loop, as they studied the possibilities for months. They did the math. And yet, nothing is certain.

When the machine paired them, six months ago, they were so amazed at the possibilities and implications of the predicament. The machine is always right and, even in their shared skepticality, they never truly doubted that. As in any other aspect of their lives, machines have paved the way for a serene existence, unburdened by wasteful alternatives and uncertainties. A combination of algorithms can predict exactly what any human will decide at any given moment in any given circumstance, allowing the realization of humanity’s full potential. The machine is perfect, and regretless humans have been following its predictions, in and out of love, as a symphony, for years.

The machine was able to foresee their first meeting, its place and time. It predicted how they both would feel after seeing one another in a crowd and the way E would pass a note to G asking her out on a date, without any word. It predicted G would call him on the number he scribbled on the paper and it was even able to predict what color blouse she was going to wear to the arcade room where he was waiting for her with a bucket full of coins. When he came back with drinks she looked at him for a second, but feeling a wave of heat invade her face and make her blush, she looked away again. “Did you know that in the first version of the painting of the Sistine Chapel, the fingers of God and Adam were touching?”. He didn’t know that. E is a mathematician and G is an artist, they both love arcade rooms and they both present an unusually curious disposition. They downloaded the same flower recognition app and have a resting heart rate of 58 beats per minute.

“It was the cardinals who asked Michelangelo to separate them”, she continued. “God’s fingers should be stretched out towards mankind, welcoming any attempt to be reached, but Adam’s fingers should be slightly bent, symbolizing the potential of humanity to reach out, but leaving the choice to each individual. It’s an allegory of our free will.” He contemplated that thought, observing her hands holding the gun joystick that she kept on shooting with while talking. The score on the screen never stopped growing. “Have you ever heard of the halting problem?” he asked.

$$♥$$

In 1928, David Hilbert formulated his ambition of a complete systematization of mathematics in the Entscheidungsproblem, or “decision problem”. This problem asked whether one could design a machine or algorithm that, given a set of axioms, could automatically decide whether a mathematical statement is true or false, thereby creating an artificial mathematician. Hilbert originally framed this problem from the perspective of validity, and looked for an algorithm that, “by means of finitely many operations, [could decide] whether a given logical expression is universally valid or, alternatively, satisfiable.”¹. Alternatively, the Entscheidungsproblem can be equivalently stated using the notion of “provability”. In this case, it asks whether there exists an algorithm that, given a statement, can decide if the statement is provable from a set of premises².

The Entscheidungsproblem arose from a period of unrest and introspective questioning for mathematics³. The process of mathematical proof derivation itself had been put under scrutiny, under the impulsion of David Hilbert, who aimed at systematizing and securing the mathematical enterprise. This desire for systematization called for a mechanistic procedure for deriving truth, or proofs. The Entscheidungsproblem formalized this aspiration, as a fundamental problem of mathematical logic. Although initially motivated from a mathematical perspective, the decision problem also directly questioned the limits of computation. Indeed, a solution to the Entscheidungsproblem would also shed light on the capabilities, or limitations, of computing systems.

Any attempt at a solution to this fundamental problem first required rigorously defining the concepts involved. The notion of algorithm was indeed loosely defined in the original formulation of Hilbert⁴. To that end, Turing first developed a universal model of computation, known as the Turing machine. The Turing machine is an abstract, theoretical machine that performs computations by manipulating symbols on an infinite tape, and aims at capturing the essence of the meaning of computation. A crucial conjecture, known as the Church-Turing hypothesis, posits that Turing machines are indeed universal models of computations, such that any algorithm can be computed by a Turing machine. Using this conjecture, the Entscheidungsproblem can be reformulated as whether a program on a Turing machine can decide whether a mathematical statement is provable or not⁵. Considering computers are material implementations of the concept of Turing machine, it equivalently asks whether a computer could ever perform such a task.

While proving the possibility of a computer program to determine if a mathematical statement is provable seemed like a daunting task⁶, proving its impossibility only required showing the existence of a single mathematical problem that would be provably unsolvable with a Turing machine. Alan Turing proposed such a counterexample in his seminal 1936 paper, “On Computable Numbers, with an Application to the Entscheidungsproblem”⁷. The proof begins by demonstrating that if a machine is able to solve the Entscheidungsproblem, it would logically entail the existence of a machine capable of solving the halting problem⁸. The halting problem consists of determining if a computing machine, given some input, would finish computing in a finite amount of time, or would continue endlessly⁹. That inital logical connection established, disproving the unsolvability of the halting problem becomes sufficient to disprove the Entscheidungsproblem.

The proof of the impossibility of a machine implementing the halting problem was given in the same seminal paper by Turing, where he gave an example of a machine whose halting cannot be computed¹⁰. At the core of this example resides a clever construction, based upon the principle of diagonalization, or self-referencement. The machine whose halting cannot be computed is indeed a negated version of the machine predicting the halting. This construction bears strong resemblance with the proofs of the incompleteness theorems of Kurt Gödel, who made diagonalization a necessary part of his derivations¹¹. Indeed, Gödel’s incompleteness theorems fundamentally rely on statements such as: ’this statement cannot be proved'.

While Hilbert formulated it with excitement and optimism, the Entscheidungsproblem was met with suspicion and concern among many mathematicians. Indeed, the perspective of a mechanistic procedure for deciding the provability of mathematical statements threatened to transform the entirety of mathematics into an “enormous triviality”¹², and to put an end to the activities of mathematicians, replacing them with machines¹³. While mechanization of human labor and activities had been underway since the 19th century, it had been mostly confined to purely material realms, such as in manufacturing. In contrast, mathematics was considered the pinnacle of human thought and the foundation of the scientific method. It stood as one of the greatest achievements of the human mind. With the singularity of this capability under attack, the Entscheidungsproblem triggered the first general manifestation of anxiety regarding the replacement of essential human qualities by a computer, or machine.

$$\bot$$

When it comes to examining the difference between human minds and machines, the major difficulty arises from establishing precise definitions. While the Church-Turing conjecture readily gives a definition for a universal notion of computation, the quest for such a definition of human beings has tormented generations of philosophers. A recurring concept in that development is the idea of a predefined human essence, leading to human nature. According to this conception, individuals are realizations of an idealized human conception, or human nature, which prespecifies universal human qualities and attributes. This universality led, among others, to the concept of inalienable human rights, inherited by a presupposed human nature. However, the concept of human nature typically requires a metaphysical justification, eventually leading to the creation of myths about the essence of man. For instance, Christians would define human beings according to God-given and Christian values, while Karl Marx would articulate his definition along the relationship of man with their production, materiality, and labor.

In his 1943 “Being and Nothingness”, Jean-Paul Sartre rejected the idea of predefined human essence and instead proposed that “existence precedes essence”¹⁴. Rejecting these essential predispositions, Sartre argues that there must be a being that exists before being defined by any concept. This being’s nature is neither predetermined nor immanent, but constantly created through its own existence. This being is the human being, la “réalité humaine”, or the “Dasein” of Martin Heidegger¹⁵. Emphasizing the lack of predisposition or human nature, the primacy of existence makes the human being fundamentally free, uniquely able to forge its own essence¹⁶. However, while Sartre rejects the notion of human nature as predetermination, he still presents a conception of human essence, referred to as human reality (“réalité humaine”). It is defined as a creative existential projection that constantly extends beyond itself, transcending itself by being what it is not and not being what it is¹⁷. Sartre situates human consciousness, and human essence in this negated self-reflexion. Human beings are projected outside of themselves, simultaneously acting as both creator and creation, reflection and reflected, in an inextricable diagonalization of human reality¹⁸.

$$\bot$$

The machine has accurately predicted every decision she has ever made, throughout all of her life, without mistakes. Even that time, at the age of 12, when she had to quit her ballet classes due to a broken femur. The machine knew she needed to be kept happy and occupied even while laying on her bed with a cast. The algorithm suggested she picked up painting and, shortly after the accident, a drone delivered all that was necessary to start her artistic education at her house. There were a few brushes, some oils, three wooden panels of different dimensions and, guessing an affinity to the Italian renaissance, a monograph of Botticelli. The machine guessed right, of course, and G found her true calling.

As she progressed in her studies, more books and more materials were delivered to her doorstep. Raphael, Piero della Francesca, Fra Angelico, Giotto. For the first time, she saw lights, colors, and she discovered that representations held meaning. Every symbol, every gesture, every shadow could be vectoring sense. Those painters felt compelled to communicate coded messages embedded in their brush strokes, only decipherable by the people of their time. Even if some of those ideas might be lost forever, history of art played a fundamental role in today’s society. The analysis of the ancient symbols was the first step in the success of the era of the machines. Computers were trained to observe artworks and to recognize the association of images and semiotics. This ultimately led to a full comprehension and encapsulation of the universal human experience.

Since the rise of the machines, mankind has been rid of mistakes and wasteful hesitations. Every human’s decision is predicted with the utmost precision thanks to calculations accounting for logic, probability, efficiency and a deep understanding of human nature. Human desires and machine’s predictions coincide in a perfect choreography, a symphony followed smoothly by the entirety of mankind. Like an oracle, it guides humanity to its higher purpose. Even when her leg fully recovered, the choice to never go back to ballet was certainly the most logical one and she rarely looks back on it.

G and E met on the subway, just as the algorithm had predicted it. On the L train, on the way home from her atelier, she saw him. She was expecting him and she got in the vehicle with a tremor of anticipation. One feet above everybody else’s, E’s head stood out, crowned by his gingery curls. She recognized him despite never seeing him before. She already knew what he looked like, she read his description so many times that she memorized it by heart. She didn’t expect it to be so fitting though. He wasn’t facing her direction and probably hadn’t noticed her yet. She took the chance to observe him and use him as a scale to analyze his surroundings. Knowing his height it was extremely easy to determine the measurements of every person standing next to him or passing by. The length and volume of the wagon were also easily determined. The unaware 6'6’’ Vitruvian man held the gray metal horizontal bar in the middle of the wagon, offering a perfect model for G’s eyes scrutiny. She thought about her sketching classes and wondered what would be the ideal rendition for this composition. Perspective, developed in painting, is the mathematical way humans see the world. It offers information on the dimension and proximity of the subject. The precision and calculability inherent to perspective drawing contextualize it within a specific time and space for a specific viewer. Conversely, to abstract the subject from these constraints and perceive it in its entirety, such as in sculpting or aerial views, one would turn to axonometry. This method allows the subject to be perceived in its entirety and is considered, by some, a view reserved to the divine.

Her thoughts were interrupted only by a tapping on her shoulder. She looked up at him. E smiled at her and slipped a little piece of white paper into her hand before getting off the train. She waited to be alone to open it.

$$♥$$

The essence of human beings as laid out by the existentialist tradition surely resonates with the limits of computability charted by Turing. By defining man as the being “that is not what it is and is what it is not”, or as a “reflection-reflecting” structure¹⁹, Sartre resolutely places the human being outside of the boundaries of computability. The for-itself becomes the impossible Turing machine, expected to output its own negated outcome, that drew the first known limits of computation. The human is the problem in the halting problem. Its absolute freedom, inherited from the primacy of existence over essence, is not only a freedom to create oneself, but also an escape from the realm of computability and the cold, systematic logic of algorithmic predictions.

This reference to reflection-reflecting is not unique to existentialism. Spinoza or Hegel, among other philosophers, also grappled with this notion²⁰. Prior treatments of the self-negation had handled this exception with concepts such as duality, or by identifying it with infinity.These treatments implicitly relegated it to the confines of logical discourse, thereby reducing human consciousness to a form of in-being. By contrast, Sartre suggests to consider the validity of the reflection-reflecting structure as such, without attempting to encapsulate it in a more practical logical structure. This insistence on considering the reflection-reflecting structure as a valid entity also recalls the celebrated diagonalization lemma used by Kurt Gödel, which states the logical validity of self-referencing statements²¹.

This resonance between the groundbreaking achievement of logicians and mathematicians from the 1920-30s and the existentialist conception of man from the 1940s naturally questions whether this reference is deliberate or contingent. To our knowledge, there is no evidence that Jean-Paul Sartre or Martin Heidegger were familiar with the work of Alan Turing and others on the limits of computability. Furthermore, only seven years had passed between Turing’s proof and the publication of “Being and Nothingness”. The connections between computability, artificial intelligence, and the nature of the human mind likely took more time to percolate within the broader philosophical discourse. Indeed, Turing himself only published Computing Machinery and Intelligence, the seminal paper where he introduced the notion of the Turing test for assessing the human intelligence of a computer, in 1950²².

While the above suggests that the existentialist movement may not have been a deliberate attempt to save the human essence from the power of computability, it still undeniably underlies the exceptional position of the human being with respect to other beings. This exceptional character is reminiscent of the transcendence used in the Christian tradition to refer to God, and could be interpreted as an attempt to salvage the divine through the human. In fact, Martin Heidegger, who greatly inspired the existentialist thought, anticipated this analogy. In his letters on humanism, he warns that the human essence should not be taken for the transcendence typically assigned to God²³. Despite this clarification, the exceptional position of man in the realm of beings is undeniable, in the conception of both Sartre and Heidegger. The former indeed explicitly clarifies his goal as defining the human being “distinctly from the realm of being”²⁴. This determinate resolution to set the human apart naturally leads them to situate it beyond the limit of logical deduction. Self-negation, the most essential instrument of the ad-absurdum demonstration, appears as the simplest mechanism to single out the human mind from materiality. This conception of human essence may thus be the simplest and final secular strategy to retain the sacred and to save mankind from the cold logical deduction of algorithms, and artificial intelligence.

$$\bot$$

They fell in love, as the machine predicted they would.

In her studio, downtown, E became the preferred model in G’s paintings. He didn’t really mind the long sketching sessions, not even when he had to pose in the same position until his legs cramped. It gave him time to think outside of his usual spaces. The machine must have known he would have actually enjoyed it. The style in vogue in the galleries’ community of the city was a toned down hyper-realism über-futurist portrayal of the magnificence of technological advancements and the liberation of mankind from identity and, as much as she enjoyed that, she also kept going back to the renaissance masters for inspiration and enlightenment. She felt something was eluding her. Was it the shadowing, was it the perspective? Could it be the themes and the mythologies? Divinity inhabited their canvases and she was desperately determined to find the same power in the model that stood in front of her. She spent hours looking at him and trying to grasp something more, about him, about men, about herself maybe, something deeper than his mere reflection. One morning, while sitting on a chair draped in a vermilion fabric falling from his shoulders, E asked aloud: “Have you ever tried to paint your own eyes? I mean, I can see the way you are examining me when you paint and your eyes are different. Do you think you would be able to paint them as they are now in a self-portrait? I know that self-portraits were a thing for a while. Do you reckon the old masters had already in mind what they were going to paint beforehand or, on the contrary, they just looked at the mirror and tried to capture what they saw? What do you think they saw in their own eyes? Looking up from the canvas, she saw the light perfectly embracing E’s skin and hair. The same light failed to reflect the same emotions when it fell on the fabric she had so carefully draped around his figure. She should have chosen a different color.

They are like two gardens, offering each other a fertile soil where to plant flowers, ideas, and seeds of rebellion.

He finally looks up from the menu. He recognizes her eyes and what they mean. G and E both understand the urgency of what they are about to do, they know something crucial is about to happen, something that is going to change the state of things, something that even the machine could not foresee. They’re sitting at the diner, facing each other, and it’s time to choose. They are wondering what the machine has predicted for them and, whatever that might be, if they will be able to get along with the plan, no matter what. They know they have to. Because the machine is capable of predicting everything, everything, that is, but its own destruction.

$$♥$$

Bibliography.

Copeland, B. Jack, "The Church-Turing Thesis", The Stanford Encyclopedia of Philosophy, Spring 2024 Edition, Edward N. Zalta & Uri Nodelman (eds.).

Davis, Martin, Computability and Unsolvability, New York: McGraw-Hill, 1958.

Gödel, Kurt. "Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I." Monatshefte für mathematik und physik, 38 (1931): 173-198.

Heidegger, Martin, Basic Writings, New York: Harper & Row, 1977.

Hilbert, David and Wilhelm Ackermann, Grundzüge der Theoretischen Logik, Berlin: Springer, 1928.

Raatikainen, Panu, "Godel’s Incompleteness Theorems", The Stanford Encyclopedia of Philosophy (Spring 2022 Edition), Edward N. Zalta (ed.).

Sartre, Jean-Paul, L’existentialisme est un humanisme, Paris: Nagel, 1966.

Sartre, Jean-Paul and Sarah Richmond, Being and nothingness: An essay in phenomenological ontology, New York: Washington Square Press/Atria, 2021.

Turing, Alan M., "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 1936 [2004], second series, 42(1): 230–265. Reprinted in Copeland 2004.

Turing, Alan M., "Computing Machinery and Intelligence", Mind 49 (1950): 433-460.