# Ehud Shapiro

Ehud Shapiro (Hebrew: אהוד שפירא; born 1955) is an Israeli scientist, entrepreneur, artist, and political activist who is Professor of Computer Science and Biology at the Weizmann Institute of Science. With international reputation, he made contributions to many scientific disciplines, laying in each a long-term research agenda by asking a basic question and offering a first step towards answering it, including how to computerize the process of scientific discovery, by providing an algorithmic interpretation to Karl Popper's methodology of conjectures and refutations; how to automate program debugging, by algorithms for fault localization; how to unify parallel, distributed, and systems programming with a high-level logic-based programming language; how to use the metaverse as a foundation for social networking; how to devise molecular computers that can function as smart programmable drugs; how to uncover the human cell lineage tree, via single-cell genomics; how to support digital democracy, by devising an alternative architecture to the digital realm grassroots.
Shapiro was also an early internet entrepreneur, and a proponent of global digital democracy.
Shapiro is the founder of the Ba Rock Band and a founder of the Israeli political party "Democratit". He is a winner of two ERC (European Research Council) Advanced Grants.

## Early life and education

Born in Jerusalem in 1955, Shapiro became acquainted with the philosophy of science of Karl Popper through a high-school project supervised by Moshe Kroy from the Department of Philosophy, Tel Aviv University. In 1979, Shapiro completed his undergraduate studies in Tel Aviv University in mathematics and philosophy. Shapiro's PhD work with Dana Angluin in computer science at Yale university attempted to provide an algorithmic interpretation to Popper's philosophical approach to scientific discovery, resulting in both a computer system for the inference of logical theories from facts; and a methodology for program debugging, developed using the programming language Prolog. His thesis, "Algorithmic Program Debugging", was published by MIT Press as a 1982 ACM Distinguished Dissertation, followed in 1986 by "The Art of Prolog", a textbook co-authored with Leon Sterling.

## Career

Moving to the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science in 1982 as a post-doctoral fellow, Shapiro was inspired by the Japanese Fifth Generation Computer Systems project to invent a high-level programming language for parallel and distributed computer systems, named Concurrent Prolog. A two-volume book on Concurrent Prolog and related work was published by MIT Press in 1987.
In 1993, Shapiro took leave of absence from his tenured position at Weizmann to found Ubique Ltd. (and serve as its CEO), an early Israeli Internet software startup. Building on Concurrent Prolog, Ubique developed "Virtual Places", a 2D metaverse and social networking software that included instant messaging, chat rooms, collaborative browsing, online events and games, and voice-over-IP. Ubique was sold to America Online in 1995, and following a management buy out in 1997 was sold again to IBM in 1998.
Shapiro attempted to build a computer from biological molecules, guided by a vision of "A Doctor in a Cell": A biomolecular computer that operates inside the living body, programmed with medical knowledge to diagnose diseases and produce the requisite drugs. Being a novice to biology, Shapiro realized his first design for a molecular computer as a LEGO-like mechanical device built using 3D stereolithography, which was patented upon his return to Weizmann in 1998. During 1999–2016, Shapiro's lab was designing and implementing various molecular computing devices.
In 2011, Shapiro designed an effective method of synthesizing error-free DNA molecules from error-prone building blocks, and founded the CADMAD consortium (Computer-Aided Design and Manufacturing of DNA libraries):
In 2005, Shapiro presented a vision of the next grand challenge in human biology: To uncover the Human cell lineage tree. The history of how the human body grows from a single cell (the fertilized egg) to 100 trillion cells is captured by the cell lineage tree. In his TEDxTel-Aviv talk "Uncovering The Human Cell Lineage Tree – The next grand scientific challenge" Shapiro described the system and results obtained with it so far, and a proposal for a FET Flagship project "Human Cell Lineage Flagship initiative" for uncovering the Human cell lineage tree in health and disease. The international Human Cell Atlas project, initiated by Shapiro's former Ph.D. student Aviv Regev, aims to address the precursor question of describing all cell types in the human body.

## Research

Popper suggested that all scientific theories are by nature conjectures and inherently fallible, and that refutation to old theory is the paramount process of scientific discovery. Shapiro's doctoral studies with Angluin attempted to provide an algorithmic interpretation to Popper's approach to scientific discovery – in particular for automating the "Conjectures and Refutations" method – making bold conjectures and then performing experiments that seek to refute them. Shapiro generalized this into the "Contradiction Backtracing Algorithm" – an algorithm for backtracking contradictions. This algorithm is applicable whenever a contradiction occurs between some conjectured theory and the facts. By testing a finite number of ground atoms for their truth in the model the algorithm can trace back a source for this contradiction, namely a false hypothesis, and can demonstrate its falsity by providing a counterexample to it.
Shapiro laid the theoretical foundation for inductive logic programming and built its first implementation (Model Inference System): a Prolog program that inductively inferred logic programs from positive and negative examples. Inductive logic programming has nowadays bloomed as a subfield of artificial intelligence and machine learning which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. Recent work in this area, combining logic programming, learning and probability, has given rise to the new field of statistical relational learning.

## Algorithmic program debugging

Algorithmic debugging was first developed by Shapiro during his PhD research at Yale University, as introduced in his PhD thesis, selected as a 1982 ACM Distinguished Dissertation. Shapiro implemented the method of algorithmic debugging in Prolog (a general purpose logic programming language) for the debugging of logic programs.
In case of logic programs, the intended behavior of the program is a model (a set of simple true statements) and bugs are manifested as program incompleteness (inability to prove a true statement) or incorrectness (ability to prove a false statement). The algorithm would identify a false statement in the program and provide a counter-example to it or a missing true statement that it or its generalization should be added to the program. A method to handle non-termination was also developed. Since then, the approach of algorithmic debugging has been expanded and applied to many programming languages.

## The Fifth Generation Computer Systems project

The Fifth Generation Computer Systems project (FGCS) was an initiative by Japan's Ministry of International Trade and Industry, begun in 1982, to create a computer using massively parallel computing/processing. It was to be the result of a massive government/industry research project in Japan during the 1980s. It aimed to create an "epoch-making computer" with-supercomputer-like performance and to provide a platform for future developments in artificial intelligence.
In 1982, during a visit to the ICOT, Shapiro invented Concurrent Prolog, a novel concurrent programming language that integrated logic programming and concurrent programming. Concurrent Prolog is a logic programming language designed for concurrent programming and parallel execution. It is a process oriented language, which embodies dataflow synchronization and guarded-command indeterminacy as its basic control mechanisms.
Shapiro described the language in a Report marked as ICOT Technical Report 003, which presented a Concurrent Prolog interpreter written in Prolog. Shapiro's work on Concurrent Prolog inspired a change in the direction of the FGCS from focusing on parallel implementation of Prolog to the focus on concurrent logic programming as the software foundation for the project. It also inspired the concurrent logic programming language Guarded Horn Clauses (GHC) by Ueda, which was the basis of KL1, the programming language that was finally designed and implemented by the FGCS project as its core programming language.

## Ubique Ltd.

In 1993, Shapiro took a leave of absence from the Weizmann Institute to found and serve as CEO of Ubique Ltd., an Israeli Internet software startup. Ubique developed an early 2D metaverse and social networking software that included instant messaging, chat rooms, collaborative browsing, online events and games, and voice-over-IP. The company's first product, Virtual Places 1.0, was developed on top of Unix-based workstations and was announced on the same day that Netscape Communications announced it browser and server products. Virtual Places 2.0 was based on Windows 95 and PCs. Ubique was sold to America Online in 1995 for $14.5 million, bought back by its management in 1997, and sold again to IBM in 1998, where Ubique's technology was the basis of IBM's SameTime instant messaging product.

## Molecular programming languages

In a paper published in 2002 in Nature magazine "Cellular abstractions: Cells as computation" Shapiro with his Ph.D. student Aviv Regev raised the question: Why can't the study of biomolecular systems make a similar computational leap? Both sequence and structure research have adopted good abstractions: ‘DNA-as-string’ and ‘protein-as-three-dimensional-labelled-graph’, respectively. They believed that computer science could provide the much-needed abstraction for biomolecular systems. Together Regev and Shapiro used advanced computer science concepts to investigate the ‘molecule-as-computation’ abstraction, in which a system of interacting molecular entities is described and modelled by a system of interacting computational entities. He developed Abstract computer languages for the specification and study of systems of interacting computations, in order to represent biomolecular systems, including regulatory, metabolic and signaling pathways, as well as multicellular processes such as immune responses.
The work (that initially used the π-calculus, a process calculus) was later taken over by IBM Cambridge in the UK (Luca Cardelli) that developed SPiM (Stochastic Pi Calculus Machine). In the last decade the field has flourished with a vast variety of applications. More recently, the field even evolved to a synthesis of two different fields – molecular computing and molecular programming. The combination of the two exhibits how different mathematical formalisms (such as Chemical Reaction Networks) can serve as 'programming languages' and various molecular architectures (such as DNA molecules architecture) can in principle implement any behavior that can be mathematically expressed by the formalism being used.

## Doctor in a cell

By combining computer science and molecular biology, researchers have been able to work on a programmable biological computer that in the future may navigate within the human body, diagnosing diseases and administering treatments. This is what Shapiro termed a "Doctor in a cell". His group designed a molecular-scale computer made entirely of biological molecules that realized a mathematical model of programmable computer termed finite automata, which used its DNA input molecule as fuel. The molecular computer was also recognized in 2003 as a Guinness World Record for the smallest molecular computing device. The molecular computer was then extended with an input and output mechanism so that it can be programmed – in a test tube – to identify molecular changes in the body that indicate the presence of certain cancers, and release a drug molecular in response in case it does. The computer was then able to diagnose the specific type of cancer, and to react by producing a drug molecule that interfered with the cancer cells’ activities, causing them to self-destruct. For this work was a member of the 2004 "Scientific American 50" as Research Leader in Nanotechnology.
In 2009, Shapiro and Ph.D. student Tom Ran presented the prototype of an autonomous programmable molecular system, based on the manipulation of DNA strands, which is capable of performing simple logical deductions. This prototype is the first simple programming language implemented on a molecular-scale. If introduced into the body, this system has immense potential to accurately target specific cell types and administer the appropriate treatment, as it can perform millions of calculations at the same time and 'think' logically.
Shapiro's team aimed to make these computers perform highly complex actions and answer complicated questions, following a logical model first proposed by Aristotle over 2000 years ago. The team has also found a way to make these microscopic computing devices 'user-friendly' by creating a compiler – a program for bridging between a high-level computer programming language and DNA computing code. They sought to develop a hybrid in silico/in vitro system that supports the creation and execution of molecular logic programs in a similar way to electronic computers, enabling anyone who knows how to operate an electronic computer, with absolutely no background in molecular biology, to operate a biomolecular computer.
In 2012, Shapiro, Tom Ran and students succeeded in creating a genetic device that operates independently in bacterial cells. The device has been programmed to identify certain parameters and mount an appropriate response. The device searches for transcription factors – proteins that control the expression of genes in the cell. A malfunction of these molecules can disrupt gene expression. In follow-up research, Benenson and his team have produced a moleciular computer that cures a certain type of cancer in mice, with the goal of producing a cancer drug based on this method.

## DNA editing

Shapiro designed an effective method of synthesizing error-free DNA molecules from error-prone building blocks. DNA programming is the DNA-counterpart of computer programming. The basic computer programming cycle is to modify an existing program, test the modified program, and iterate until the desired behavior is obtained. Similarly, the DNA programming cycle is to modify a DNA molecule, test its resulting behavior, and iterate until the goal (which is either understanding the behavior or improving it) is achieved.
Shapiro founded the CADMAD consortium, which aimed to deliver a revolution in DNA processing analogous to the revolution text editing underwent with the introduction of electronic text editors.This goal was eventually achieved by others and with a different technology – CRISPR gene editing.

## Human cell lineage tree

In 2005, Shapiro and students presented a vision of the next grand challenge in Human biology: To uncover the Human cell lineage Tree. Inside each person is a cell lineage tree.
The challenge of uncovering the Human Cell Lineage Tree is reminiscent, both in nature and in scope, to the challenge faced by the Human Genome Project at its inception and, in fact, its results will decisively contribute to the functional translation and ultimate understanding of the genome sequence. A technological leap of a magnitude similar to the one that occurred during the Human Genome Project is required for the success of the human cell lineage project, and the biological and biomedical impact of such a success could be of a magnitude similar, if not larger than that of the Human Genome Project. In his TEDxTel-Aviv talk "Uncovering The Human Cell Lineage Tree – The next grand scientific challenge" Shapiro described the system and results obtained with it so far, and a proposal for a FET Flagship project "Human Cell Lineage Flagship initiative" for uncovering the Human cell lineage tree in health and disease. The goal of Human Cell Atlas project launched in 2016 by Shapiro's former Ph.D. student Aviv Regev and colleagues, is to identify the cell types in the human body. It is a necessary precursor to identifying the human cell lineage tree.

## Equality in digital democracy

The Internet has revolutionized almost every domain of human endeavor, but not democracy. Puzzled by this singularity, Shapiro set to explore how an Internet revolution of democracy could take place. Consulting a founding document of modern democracy, the French 1789 Declaration of the Rights of Man and Citizen, Shapiro distilled from it the values that would need to be upheld by any digital democracy, with equality being first and foremost.
Subsequently, Shapiro and his team at Weizmann addressed the many dimensions of equality in digital democracy: Equality in voting, via Sybil-Resilient Social Choice [ref], which aims uphold democratic voting despite the penetration of sybils (fake and duplicate identities) into a digital community; equality in proposing; equality in deliberation and coalition formation; equality in constitution formation; and equality in community forking.

## Grassroots digital democracy

Equality in governance of a digital community is meaningful only it also applies to the platform on which the community operates. The digital realm is dominated today two types of platforms: autocratic server/cloud-based (e.g. Facebook), and plutocratic proof-of-work/stake-based (e.g. Bitcoin/Ethereum), and, and lacks a democratic alternative. To help remedy this, Shapiro presents a third alternative architecture for the digital realm, termed "grassroots digital democracy". Informally, a distributed system is grassroots if it can have autonomous, independently-deployed instances — geographically and over time — that can interoperate once interconnected. An example would be a servereless smartphone-based social network supporting multiple independently-budding communities that merge when a member of one community becomes also a member of another.
Grassroots applications may allow people to conduct their social, economic, civic, and political lives in the digital realm solely using the networked computing devices they own and operate (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or value-extraction (e.g., by global digital platforms such as Facebook or Bitcoin).
Shapiro initiated in 2012 and led the "open party" (later "open community") project within the Public Knowledge Workshop, which aimed to provide foundations for the operation of an e-party espousing direct democracy via the internet [ref in source]. He further extended his concepts of e-democracy in his 2016 WEF lecture and Financial Times Opinion article. In 2020 he founded the political party Democratit - freedom, equality and fraternity.