Reflexivity and the diagonal argument in proofs of limitative theorems

Details Reflexivity and the diagonal argument in proofs of limitative theorems Reflexivity and the diagonal argument in proofs of limitative theorems

2011-11-29

arxiv.org/abs/1111.6954v1

Computer Science

Logic in Computer Science

10 pages, 2 figures

Scientific paper

This paper discusses limitations of reflexive and diagonal arguments as methods of proof of limitative theorems (e.g. G\"odel's theorem on Entscheidungsproblem, Turing's halting problem or Chaitin-G\"odel's theorem). The fact, that a formal system contains a sentence, which introduces reflexitivity, does not imply, that the same system does not contain a sentence or a proof procedure which solves this problem. Second basic method of proof - diagonal argument (i.e. showing non-eqiunumerosity of a program set with the set of real numbers) does not exclude existance of a single program, capable of computing all real numbers. In this work, we suggest an algorithm generating real numbers (arbitrary, infinite in the limit, binary strings), and we speculate it's meaning for theoretical computer science.

Affiliated with

Also associated with

No associations

Rating

Reflexivity and the diagonal argument in proofs of limitative theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reflexivity and the diagonal argument in proofs of limitative theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reflexivity and the diagonal argument in proofs of limitative theorems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6202