## Can a Wish produce a paradox?

I have an idea for a cool chaotic BBEG. His/her ultimate goal is to completely destroy existence.

Could a Wish be cast in such a way as to create a paradox, allowing me to destroy existence? Or does the wish “altering reality” part of the spell indicate that it cannot produce a paradox?

For example, “I wish I was never born”?

## Formal semantics of this “paradox” subroutine?

In Section “Routines as Parameters: An Example” of the book “Algorithmics: The Spirit of Computing (3rd Edition; Page 53-54)” by David Harel and Yishai Feldman, the authors describe the routines which are allowed to accept routines as parameters. For example,

subroutine P-with-parameter-V
(1) call V-with-parameter-V, placing returned value in $$X$$
(2) if $$X = 1$$ then return with 0; else return with 1.

But what will our confused processor do when asked to carry out the following initial call to P:
call P-with-parameter-P

Then the authors explain why “serious semantical problems arise” as follows:

Syntactically, everything is fine; the routines are all called with the right syntax and the right kinds of parameters. Nevertheless, there is a paradox embodied in the very question. It is impossible that the call returns 0, because by the definition of the body of P, the value returned is 0 if a call to V-with-parameter-V (which is now really a call to P-with-parameter-P) returns 1. So, the call can return 0 only if it returns 1, which is ridiculous! A similar argument shows that the P-with-parameter-P call cannot return 1 either, but by the text of P it cannot return anything other than 0 or 1. So what does it do? Does this strange call entail an endless seesaw process? Is it simply forbidden by the language? Neither of these suggestions sounds quite right. With the first we might want to see the infinite nature of the execution reflected more explicitly in the text. The second is even worse, since it is not clear how to characterize the forbidden programs syntactically. Obviously, a formal semantics to such a language must imply precise and unambiguous answers to such questions.

I am curious: How do programming languages (especially functional programming languages such as Haskell) “resolves” this “paradox”? Is it possible to write subroutines like P-with-parameter-V in (real) programming languages? If so, what is its formal semantics?

## Metagame Paradox: what is wrong with this explanation?

Today I’ve heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post content: definition – proposed solution – conclusion)

Something is a game iff:

G1. Two players G2. Players alternate G3. The game finally ends. 

The metagame is:

M1. First player picks a game M2. Second player starts the game M3. The winner is the winner of the game at step 2. 

Example of a metagame:

1) I pick tic-tac-toe 2) OK, I put X here .. .. so they play .. 3) .. and let player 2 wins in the tic-tac-toe => player 2 wins the metagame. 

If metagame is a game, then at point (M1) both players can always pick a metagame, so the metagame will never end => (G3) is violated => metagame is not a game => contradiction.

(also contradiction for case “metagame is not a game” — metagame will satisfy the definition of a game)

What is the solution to the paradox?

UPDATE: You may want to skip this explanation and go directly to D.W. answer.

I came up with the following explanation:

Lets formalize the problem using Turing Machines notations. Let a game be a finite binary string that describes “somehow” game rules. Let a game simulator be a non-deterministic TM that reads a description from the input (without any sanity checks, so the TM doesn’t know if the game finally ends), and then makes non-deterministic moves for the first and second player. Here we assume (A1) that the game-simulator can decide valid next moves.

Now have a look at the description of a meta-game:

M1. First player picks a game 

This sentence means that we can “pick a game”, i.e. in the definition we assume (A2) that whether an arbitrarily binary string is a game (satisfies G1,G2,G3) is decidable. (see also note (n1) )

M2 and M3 look decidable.

So, my suggestion is that metagame is not “defined properly”, since its definition assumes the existence of a decider “if a given binary string is a game”. And then we derive a contradiction, so this assumption is wrong.

Does it make sense? Is this related with other explanations of the paradox? (intuitive answers would be great!)

Notes:

1. Assuming “whether an arbitrarily binary string is a game” may be too much. But we need some computable procedure “pick a game” and one that came into mind is “generate random string, check if it is a game”.
2. I don’t know what is a formal word for “not defined properly”
3. Assumption A1 may also be undecidable, but I believe it should not change the argument..

I’m writing a simulator which checks how many balls we need to occupy every box or how many balls we need for any box has at least 2 balls (birthday paradox). I wrote the script in python and it is so slow. My friend wrote a program in C++ and the script is much faster. For boxes_max_num = 1000 it takes few minutes when in my python script it takes ‘eternity’.

There is my code:

import numpy as np import matplotlib.pyplot as plt   def check_every_box_is_occupied(boxes):     for box in boxes:         if box == 0:             return False     return True   def check_birthday_paradox(boxes):     for box in boxes:         if box >= 2:             return True     return False   def main():     number_of_tests = 250     birthday_paradox_graph = [[], []]     every_box_is_occupied_graph = [[], []]     boxes_max_num = 1000     for number_of_boxes in range(10, boxes_max_num + 1, 1):         print(number_of_boxes)         average_frequency_birthday_paradox = 0         average_frequency_every_box_is_occupied = 0         for index in range(number_of_tests):             number_of_balls = 1             boxes = np.array([0] * number_of_boxes)             while True:                 boxes[np.random.randint(number_of_boxes)] += 1                 if check_birthday_paradox(boxes):                     average_frequency_birthday_paradox += number_of_balls                     break                 number_of_balls += 1             number_of_balls = number_of_boxes             boxes = np.array([0] * number_of_boxes)             while True:                 boxes[np.random.randint(number_of_boxes)] += 1                 if check_every_box_is_occupied(boxes):                     average_frequency_every_box_is_occupied += number_of_balls                     break                 number_of_balls += 1          plt.rcParams.update({'font.size': 15})         birthday_paradox_graph[0].append(number_of_boxes)         birthday_paradox_graph[1].append(average_frequency_birthday_paradox / number_of_tests)         every_box_is_occupied_graph[0].append(number_of_boxes)         every_box_is_occupied_graph[1].append(average_frequency_every_box_is_occupied / number_of_tests)     plt.figure(1)     plt.plot(birthday_paradox_graph[0], birthday_paradox_graph[1], 'ko')     plt.title("Conajmniej jedna urna ma conajmniej dwie kule")     plt.xlabel("Liczba urn")     plt.ylabel("Średnia liczba kul potrzebna do spełnienia warunku")     plt.figure(2)     plt.title("Wszystkie urny są zapełnione")     plt.xlabel("Liczba urn")     plt.ylabel("Średnia liczba kul potrzebna do spełnienia warunku")     plt.plot(every_box_is_occupied_graph[0], every_box_is_occupied_graph[1], 'ko')     plt.show()  if __name__ == '__main__':     main() 

Can you help me to improve the code to make it faster? Is it possible in raw python?

## The barbers paradox first order logic formalization

I tried to look on the site and while I found some similar questions, I did not find the first order logic formalization of the following sentence (the basic barber’s paradox), so I wanted to ask if I got the right first order logic formalization of it, and I am sure others will benefit from this thread as well.

Sentence: there exists a barber who shaves all the people that don’t shave themselves.

My attempt: this complicated sentence can be made simpler by inferring that “for all of those who does not shave themselves, are shaved by the barber”

And now it seems to be easier to substitute with variables so:

$$\exists x(\lnot S(x,x) \rightarrow S(b,x))$$

where $$S(x,x)$$ is shaving(verb), $$x$$ are the persons (who don’t shave themselves), and $$b$$ is a shortcut for barber, so if a person does not shave himself, it can be inferred that he is shaved by the barber.