Consider this game.
You have a perfect ruler and a perfect protractor. You are also able to observe perfectly if two lines are parallel.
Is it possible to prove that a given quadrilateral is a square, using exactly 3 steps?
For example, a proof using 4 steps would be this.
Observe that opposite sides are parallel (two steps).
The angle between the diagonals is 90 degrees.
The angle between any two adjacent sides is 90 degrees.
My gut feeling is that it is not possible to do this in 3 steps and that the minimum would be 4. But how would one prove this?
If you can construct lines and verify angels being 90 degrees this is enough. If a quadrilateral has 90 degree angle corners and the diagonal meets in 90 degree angle then it's a square.
First if it's corners are 90 degrees then it's by definition a rectangle. To see that the angle between the diagonals seals the deal you observe that the triangles formed by the diagonals must be isoscele with all having the same length of the sides with same length (because they share these sides with it's neighbor). So the angle between the equal sides is given by trigonometry of the length of this side and the opposite side of the rectangle. If and only if those are equal the angles are equal and they always sum up to 360 (so they must be 90 if and only if they're equal).
Another method is to compare the length of the sides and diagonals (only needing compass). A quadrilateral is a square if and only if the sides are equal and the diagonals are equal. By definition you have a rhombus if and only if the sides are equal. The rest is seen because you will use this to form congruent triangles (which must have the same angles) so the corners of the rhombus must have the same angles and they sum up to 360 degrees (reversely if it's a square you form equal triangles with the diagonals because two sides are the same and the angle between them are the same, that will make the diagonals the same).
If you by "step" mean to measure a length or angle then you will need at least four steps (I think, well almost at least). According to this definition your solution may use more steps as checking that two lines are parallell is done with two measurements (my first solution can be done in four such steps as you only have to measure three corners and one angle between the diagonals). Sloppliy speaking this is because a quadrilateral to be congruent with another five quantities of it need to match and for them to be similar four has to match (or five have to be "proportional"). And a derived quantity (that) depends continuously is just a matter of degrees of freedom.