ZK in Context - Part 4

Ali Atiia

yAcademy, yAudit

https://twitter.com/AliAtiia_

yAcademy

https://yacademy.dev/fellowships

(2) Accepted few self-evident Truths (axioms)

If:

(1) We started off with some set of alphabet like :

(3) Unambiguously defined the rules of derivation

Is there a guarantee that every conceivable language (=Truth, “problem”) is expressible thru? (completeness)

0 s ¬ ∀ ∃ = ( ) + ⨉ ∨ x₁ x₂ x₃ …

Last time:

(2) Accepted few self-evident Truths (axioms)

If:

(1) We started off with some set of alphabet like :

(3) Unambiguously defined the rules of derivation

Is there a guarantee that no false statement cannot be arrived at by valid application of rules of derivation? (consistency)

0 s ¬ ∀ ∃ = ( ) + ⨉ ∨ x₁ x₂ x₃ …

Last time:

(2) Accepted few self-evident Truths (axioms)

If:

(1) We started off with some set of alphabet like :

(3) Unambiguously defined the rules of derivation

Is there a guarantee that the truthfulness or falsehood of a statement can be determined by direct unambiguous mechanical application of the rules of derivation? (decidability)

0 s ¬ ∀ ∃ = ( ) + ⨉ ∨ x₁ x₂ x₃ …

Last time:

Gödel’s reduction answered the first 2 questions

4) Construct a meta-statement that cannot be proven within the system

3) Arithmetized proofs into unique integers ∏₁, ∏₂, …. ∏_∞

2) Arithmetized statements into unique integers n₁, n₂, …. n_∞

1) Encoded the alphabet

❌ Completeness

❌ Consistency

? Decidability

Today: Decidability

7

Is there a Universal language ? A language of all languages ?

Is there a Universal machine?

8

Universal machine:

• aware of the axioms of universal language
• faithful to the rules of universal language

​

Is there a Universal language ? A language of all languages ?

Is there a Universal machine?

9

Nothing special about this machine really, when consulted about whether a number is IN our OUT, it consults the axioms and applies the rules mechanically

​

e.g. recall the machine sketched above for the P-E language has no conception of “addition”

Is there a Universal language ? A language of all languages ?

Is there a Universal machine?

Universal machine:

• aware of the axioms of universal language
• faithful to the rules of universal language

​

10

Is there a Universal machine?

Is there a Universal language ?

11

Is there a Universal machine?

Is there a Universal language ?

Let’s settle for a universal language (in small letters) ..

​

(ignore those logical blackholes, when was the last time someone bumped into one anyway, practically speaking ? )

12

Is there a Universal machine?

Is there a Universal language ?

Let’s settle for a universal language (in small letters) ..

​

the most widely used “universal language” in practice is ZFC set theory (13 axioms)

�We used it to define SAT, Knapsack, EC, 3-coloring…

(ignore those logical blackholes, when was the last time someone bumped into one anyway, practically speaking ? )

13

universal language = all Truths (minus some weird “problematic statements”)

​

Is there a Universal machine?

Is there a Universal language ?

Let’s settle for a universal language (in small letters) ..

14

universal language = all Truths (minus some weird “problematic statements”)

​

universal language can describe everything, including machines

Is there a Universal machine?

Is there a Universal language ?

Let’s settle for a universal language (in small letters) ..

15

Every conceivable sentence

Every conceivable machine

∞

∞

16

Every conceivable sentence

Every conceivable machine

∞

∞

Recall the encoding of the P-E language�and its corresponding decider machine, �both encoded as natural numbers

17

Every conceivable machine

∞

∞

This is the result returned by

machine encoded with 2 when supplied with statement encoded with 1 as input

Every conceivable sentence

18

∞

∞

Consider machine number k which �operates as follows:

19

∞

∞

Consider machine number k which �operates as follows:

1. It receives sentence n

20

∞

∞

Consider machine number k which �operates as follows:

1. It receives sentence n

2. It feeds sentence n to machine n

21

∞

∞

Consider machine number k which �operates as follows:

1. It receives sentence n

2. It feeds sentence n to machine n

3. It adds 1 to the result (diagonal+1)

22

∞

∞

Consider machine number k which �operates as follows:

1. It receives sentence n

2. It feeds sentence n to machine n

3. It adds 1 to the result (diagonal+1)

4. It terminates

23

∞

∞

m_k (n) = m_n (n) + 1

In other words, in shorthand notation :

Consider machine number k which �operates as follows:

1. It receives sentence n

2. It feeds sentence n to machine n

3. It adds 1 to the result (diagonal+1)

4. It terminates

24

∞

∞

What happens if we supply sentence k itself to m_k ?

25

∞

∞

m_k (k) = m_k (k) + 1

What happens if we supply sentence k itself to m_k ?

26

∞

∞

m_k (k) = m_k (k) + 1

What happens if we supply sentence k to m_k ?

(!)

Logical blackhole, so m_k does not, could not, exist!

27

m_k (k) = m_k (k) + 1

(!)

Logical blackhole, so m_k does not, could not, exist!

Therefore, there exist at least one language that is beyond decidability

28

m_k (k) = m_k (k) + 1

(!)

Logical blackhole, so m_k does not, could not, exist!

Notice we didn’t even need to to define the internal of the machine (or the intricate details of an algorithm accepting and simulating other algorithms) in order to reach this undecidability result

29

No

Some Truths are beyond provability

No

There are more languages than there are machines to decide them!

Is there a Universal machine?

Is there a Universal language ?

30

No

There are more languages than there are machines to decide them!

Is there a Universal machine?

• These are questions about the the foundation of mathematics itself

​

• Computer Science was born out of answers to these questions

No

Some Truths are beyond provability

Is there a Universal language ?

❌ Completeness

❌ Consistency

❌ Decidability

fuck it we ball

screw it, we tried

Whatever the axiomatic system, some truths are beyond decidability

33

Decidability: a finite and unambiguous set of instructions (algorithm) that terminate with a yes (true) or no (false)

Whatever the axiomatic system, some truths are beyond decidability

34

What we have proven so far is “there exists at least one language (diagonal+1) that no machine can decide. Other “natural” undecidable languages exist. Classic example (the halting problem):

for arbitrary j, print “yes” if m_j terminates with an answer -any answer- on every input

Whatever the axiomatic system, some truths are beyond decidability

Decidability: a finite and unambiguous set of instructions (algorithm) that terminate with a yes (true) or no (false)

35

36

ljk

Philosophy/Theology

​

Mathematical truths

​

Provability boundary

​

Decidability boundary

​

37

Chess

Protein folding

Eact Cover, 3-SAT, Knapsack, 3-Coloring

​

Arithmetic, sorting

38

Eact Cover, 3-SAT, Knapsack, 3-Coloring

39

Chess

Protein folding

Complexity Hierarchy: the closer the language is to this boundary, the harder (more computationally expensive) it is for a decider to tell who is IN and who is OUT

Eact Cover, 3-SAT, Knapsack, 3-Coloring

​

Arithmetic, sorting

40

Complexity Hierarchy is to computer scientists what the Periodic Table is to physicists

41

We classify problems within the black boundary (decidable) according to the computational resources that must be expended to solve them:

Easy classes:

• problems that require constant resources regardless of the input
• problems that require ~n^k resources, n = input size, k=constant

42

We classify problems with the black boundary (decidable) according to the computational resources that must be expended to solve them:

Hard classes:

​

• problems that require ~2ⁿ resources, n = input size

43

Another way of describing these classes:

problems that can be decomposed into two computations:

• a search that takes ~2ⁿ resources, n = input size
• a verification that takes ~log(w) resources