[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

As a computer science theorist, I want to thank Japanese polices #47

Open
johnmave126 opened this issue Mar 9, 2019 · 5 comments
Open

As a computer science theorist, I want to thank Japanese polices #47

johnmave126 opened this issue Mar 9, 2019 · 5 comments

Comments

@johnmave126
Copy link
johnmave126 commented Mar 9, 2019 •
edited
Loading

tl;dr: Japanese polices have just solved the halting problem

Background

Definition: Halting problem is: Given any Turing Machine M and an input s, decide whether M(s) halts.

In common words, halting problem is saying, given a program, and some inputs, determining whether the program exits at all.

In 1936, Alan Turing proved that there is no hope we can write a program to solve such a problem. But now in 2019, with the help of Japanese polices, we can actually solve halting problem in an elegant way.

Proof

Given any Turing Machine M and an input s, consider the following procedure:

  1. Write javascript that simulates M, since javascript is a Turing-complete language, it is easy to do so.
  2. For each statement of your code, append alert('!'); after it.
  3. Embed the code into some webpage and get a link
  4. Post the link on Japanese discussion boards and @ Japanese polices
  5. Sit at home and wait
  6. If you are arrested, we know M(s) never halts, otherwise M(s) halts

Now, if M(s) halts, then we are not posting a link with infinite alerts, so there is no ground for Japanese polices to arrest us. Otherwise M(s) never halts, then they will raid us and we will learn that M(s) must halt. Hence, Japanese polices are the oracle for the halting problem. ∎

Yay! We have tackled the impossible!

Caveat: Statute of limitations applies, and wiki says the Japanese statue of limitations is as long as 30 years. So we may need to sit at home for 30 years to wait for the result. But luckily, we can solve many problems at once.

It is really thrilling to be born at this time to witness such a breakthrough in computablility theory. I think Japanese polices should get the next Turing award for their fantastic job.
@Coinhiveuser
Copy link
Coinhiveuser commented Mar 9, 2019 •
edited
Loading

That is the statute of limitations (of the punishment) [刑の時効] which applies to the case it takes time for confirmation of penalty/pronouncement of penalty to the execution of the sentence.

Do you mean statute of limitations (of the prosecution) [公訴時効]?
This applies to the case which the prosecutor can't prosecute the accused when a certain period of time has passed since the crime was over.

According to “Crimes Related to Electromagnetic Records of Unauthorized Commands (Chapter XIX-2, Penal Code, known as “crimes regarding computer viruses”)”,
"Unauthorized Creation/Provision of Electromagnetic Records of Unauthorized Commands" shall be punished by imprisonment with work for not more than 3 years or a fine of not more than 500,000 yen.

The statute of limitations (of the prosecution) of the crime which has a maximum penalty for 3 years imprisonment, is 3 years, not 30 years.
(30-years statute of limitations only applies to life imprisonment with work or life imprisonment.)

You have 3-years to wait.

@yuta0801
Copy link
Collaborator
yuta0801 commented Mar 9, 2019

We can also create "let-police-solve" repo and post many implementations!

@AmaneTsukishiro
Copy link
AmaneTsukishiro commented Mar 9, 2019 •
edited
Loading

Theorem

Every definable set of programs is one-to-one reducible to Japanese polices.

Proof

Let φ(P) be a formal statement which asserts something about the program P. Given a program P, distribute the program P attached with a readme.txt "φ(P) is true". Then φ(P) is true if and only if Japanese polices consider the distribution is not criminal according to the Article 168-2. □

@AmaneTsukishiro
Copy link

Considering the halting problem relativised to the Japanese police HaltJPPolice brings a contradiction, because JPPolice computes HaltJPPolice in the same way...

@johnmave126
Copy link
Author

Considering the halting problem relativised to the Japanese police HaltJPPolice brings a contradiction, because JPPolice computes HaltJPPolice in the same way...

Which means the arithmetical hierarchy collapses contradicting an unconditional result based on Peano Arithmetic. This might mean that Peano Arithmetic is not a good set theoretical model in real life...

We might need JPPolice Arithmetic as our standard arithmetic model!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@AmaneTsukishiro @johnmave126 @yuta0801 @Coinhiveuser