Imagine one has no work permit and enters Germany with a tourist visa or a job seeker visa or a student visa. Is it legal to be a tutor? What are the legal consequences of tutoring? e.g. may one be deported or have troubles with next visa? I think that it is a minor crime so it is not de facto punishable. Will one obtain some fines(how much?) or be charged with something?
The answers to your question depend on your citizenship, whether you have a visa, and what type of visa. Illegal working is not considered a ‘minor crime’ in any jurisdiction. Assuming you are not an EU citizen, in simple terms:
Tourist visa/visa-free national: working is not permitted. The consequences of non-compliance can be severe for all concerned - a fine of up to €5000 and possibly imprisonment. Deportation proceedings for the foreign national illegal worker. https://www.zoll.de/EN/Businesses/Work/Foreign-domiciled-employers-posting/Residence-title/Consequences-of-non-compliance/consequences-of-non-compliance_node.html
Job seeker visa: as the name implies, this allows you to enter Germany to search for work during a stay of up to 6 months. It does not mean you can start working immediately without the relevant work visa/permit https://www.germany-visa.org/job-seeker-visa/
Student visa: working alongside your studies is permitted within certain limits https://www.topuniversities.com/student-info/careers-advice/how-work-germany-during-or-after-your-studies