Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




Seminars "Proof Theory" and "Logic Online Seminar"
April 15, 2024 18:30, Moscow, Steklov Mathematical Institute (8 Gubkina), room 313 + Zoom
 


How (not) to Compute the Halting Probability or Validate the Heuristic Principle

S. Salehi

University of Tabriz
Video records:
MP4 558.7 Mb
MP4 938.1 Mb

Number of views:
This page:136
Video files:45



Abstract: Two important achievements of Chaitin will be discussed: the Omega number, which is claimed to be the halting probability of randomly given input-free programs, and the heuristic principle, which is claimed to hold for program-size complexity. Chaitin's heuristic principle says that the theories cannot prove the heavier sentences; the sentences and the theories were supposedly weighed by various computational complexities, which all turned out to be wrong or incomplete. In this talk, we will introduce a weighting that is not based on any computational complexity but on the provability power of the theories, for which Chaitin's heuristic principle holds true. We will also show that the Omega number is not the claimed probability of halting (the randomly given input-free programs). We will investigate the mathematical result that is guilty of this fallacy: the Kraft-McMillan inequality.

Language: English
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024