# 2021 BigData System HW1

Question
1. Analyze the correctness/accuracy of the statement: A program that is used to decide whether or not another program will harm humans is uncomputable.

Ans: No, uncomputable.
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

For any program f that might determine if programs halt, a "pathological" program g, called with some input, can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case. A key part of the proof is a mathematical definition of a computer and program, which is known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first cases of decision problems proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.

Jack Copeland (2004) attributes the introduction of the term halting problem to the work of Martin Davis in the 1950s.

For example, in pseudocode, the program

while (true) continue
does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program

print "Hello, world!"
does halt.

2. Design a hybrid privacy-preserving system:

Merkle Tree 驗證過程可加上 ZKP 近一步保護個資
如果要證明年齡 > 18 (91年前出生)，不用提供詳細出生年份
Proof :
90 < 91
Hash(90) = 709f9ea8
Private data:
90