#logic

Is there an algorithm that, given the code of any program and an input, correctly decides whether the program eventually halts on that input? Prove your answer.

Is there an algorithm that takes any polynomial equation with integer coefficients, in any number of unknowns, and decides whether it has a solution in integers?

Let $\vee$ be a commutative and associative binary operation and $\neg$ a unary operation on a set, satisfying Robbins's equation $\neg (\neg (a\vee b)\vee \neg (a\vee \neg b))=a$ for all $a,b$. Prove that the structure is a Boolean algebra, or find a counterexample.

100 prisoners are put in separate cells and taken one at a time, in an order chosen by the warden, to a room with a light switch that is initially off. Every prisoner will be brought to the room again and again, but no one learns anything except the state of the switch. On each visit a prisoner may…