What the theorems of Incompleteness or Undecidability assert...

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Scott Mayers wrote: Fri Mar 01, 2019 12:06 am Note, if you opt to read Turing's paper, his pre-requisite is that the system is "circle-free". The author of Turing Essentials didn't seem to understand what he meant correctly but it refers to dismissing repeat decimals as rationals, such as 1/3 = 0.33333.... To do this, he required the tape he used to not be connected in a literal circle which would force it to be 'finitely' limited.
This is not a relevant detail. A circle-free tape in a finite universe is still finite. It is actually a worse design because it makes memory-access latency way worse than it needs to be.

If it's a circle you can go clock-wise or counter-clock-wise. Shortest path optimization.
Scott Mayers
Posts: 1692
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

Logik wrote: Fri Mar 01, 2019 12:21 am
Scott Mayers wrote: Fri Mar 01, 2019 12:06 am Note, if you opt to read Turing's paper, his pre-requisite is that the system is "circle-free". The author of Turing Essentials didn't seem to understand what he meant correctly but it refers to dismissing repeat decimals as rationals, such as 1/3 = 0.33333.... To do this, he required the tape he used to not be connected in a literal circle which would force it to be 'finitely' limited.
This is not a relevant detail. A circle-free tape in a finite universe is still finite. It is actually a worse design because it makes memory-access latency way worse than it needs to be.

If it's a circle you can go clock-wise or counter-clock-wise. Shortest path optimization.
Sorry, you missed my meaning. The proof he uses requires having an initial Turing Universal Machine (a general purpose computer) that can solve an infinite set of problems. If you begin with a finite machine (a limited memory space), it can't technically ever be able to solve all problems. So he set up an imaginary tape that is not linked end to end to represent an infinity of INPUTS and OUTPUT possibilities. We can do this finitely only if we reconstruct our computers in real life in a similar way to biology (component neurons that are 'born', 'grow', 'shrink', or 'die' where needed.) Our computers are actually 'finite machines' that are 'universal' but limited to the sizes of their fixed registers. The fixed registers limit the maximum size of memory space, which acts to both hold data AND act as portals (ports) as 'inputs and outpusts'.

The proof required listing all possible programs to infinity with infinite data spaces for memory that act as both input and output. You can't allow the data to alter such as a normal ports or you can't quantify all possible programs without running into possible repeats. For instance, if you allow the internet to be included in the design, you technically only require one REAL input space, such as our cable line provides serially as data input and output. But because such relatively unpredictable inputs can have repeats, we cannot count all possibilities without running into repeats (meaning we'd count what may be only one unique program as a potential infinite separate programs.

The use of a non-cycling tape also permits you to count each FINITE instance of repeated data. So, we count, 0.30000... as distinct from 0.33000...., etc, rather than confuse them all for meaning 0.33333... . If we allowed the tape to loop, the computer might be programmed to write 0.3 once, but when re-read, it might come out as 0.333333.... without being able to halt. It would not appropriately thus be able to print out what we actually put in.

So the 'circle-free' limitation is to mean that the tape used in his machine is an imaginary infinite one in both directions. Then, a number like ....00003000... is uniquely counted as ONE program, not an infinity of them.

Sorry if this is only adding to the confusion. But Turing was using language that we would mistranslate today for lacking the same identical background he assumed other readers of his day already knew within the field of logic. Even Bertrand Russell is now a tougher read today without learning a lot of their era's terminology and common educational prerequisites assumed. [They used that bottom-up approach we don't use today and a top-down strategy, though more practical now, uses a different approach that we can relate to better to our own era's expectations.]
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Scott Mayers wrote: Fri Mar 01, 2019 5:41 pm
Logik wrote: Fri Mar 01, 2019 12:21 am
Scott Mayers wrote: Fri Mar 01, 2019 12:06 am Note, if you opt to read Turing's paper, his pre-requisite is that the system is "circle-free". The author of Turing Essentials didn't seem to understand what he meant correctly but it refers to dismissing repeat decimals as rationals, such as 1/3 = 0.33333.... To do this, he required the tape he used to not be connected in a literal circle which would force it to be 'finitely' limited.
This is not a relevant detail. A circle-free tape in a finite universe is still finite. It is actually a worse design because it makes memory-access latency way worse than it needs to be.

If it's a circle you can go clock-wise or counter-clock-wise. Shortest path optimization.
Sorry, you missed my meaning. The proof he uses requires having an initial Turing Universal Machine (a general purpose computer) that can solve an infinite set of problems. If you begin with a finite machine (a limited memory space), it can't technically ever be able to solve all problems. So he set up an imaginary tape that is not linked end to end to represent an infinity of INPUTS and OUTPUT possibilities. We can do this finitely only if we reconstruct our computers in real life in a similar way to biology (component neurons that are 'born', 'grow', 'shrink', or 'die' where needed.) Our computers are actually 'finite machines' that are 'universal' but limited to the sizes of their fixed registers. The fixed registers limit the maximum size of memory space, which acts to both hold data AND act as portals (ports) as 'inputs and outpusts'.

The proof required listing all possible programs to infinity with infinite data spaces for memory that act as both input and output. You can't allow the data to alter such as a normal ports or you can't quantify all possible programs without running into possible repeats. For instance, if you allow the internet to be included in the design, you technically only require one REAL input space, such as our cable line provides serially as data input and output. But because such relatively unpredictable inputs can have repeats, we cannot count all possibilities without running into repeats (meaning we'd count what may be only one unique program as a potential infinite separate programs.

The use of a non-cycling tape also permits you to count each FINITE instance of repeated data. So, we count, 0.30000... as distinct from 0.33000...., etc, rather than confuse them all for meaning 0.33333... . If we allowed the tape to loop, the computer might be programmed to write 0.3 once, but when re-read, it might come out as 0.333333.... without being able to halt. It would not appropriately thus be able to print out what we actually put in.

So the 'circle-free' limitation is to mean that the tape used in his machine is an imaginary infinite one in both directions. Then, a number like ....00003000... is uniquely counted as ONE program, not an infinity of them.

Sorry if this is only adding to the confusion. But Turing was using language that we would mistranslate today for lacking the same identical background he assumed other readers of his day already knew within the field of logic. Even Bertrand Russell is now a tougher read today without learning a lot of their era's terminology and common educational prerequisites assumed. [They used that bottom-up approach we don't use today and a top-down strategy, though more practical now, uses a different approach that we can relate to better to our own era's expectations.]
I understood you just fine. And the implications of the above is that this is probably the most hated problem by all mathematicians:

Let P = Integer value from 1 to infinity.
Let FloatingPoint have precision of P
Let A = FloatingPoint(1.0)
Let B = FLoatingPoint(0.99999999999999.....) with precision P decimal places

Theorem 1: For all P: A !=B => True
Theorem 2: For all P: A == B => False

Theoreticians have absolutely NO idea how to deal with reality. None whatsoever. And so I LOVE putting them in a corner where they have to make trade-offs. If you are in a theoretical realm - you have no mechanism to. A doctor knows how to make trade-offs. Whatever you do - don't kill the patient!

A mathematician has no axe over his head - so he doesn't know how to make such decisions.

The above problem is the precision-range trade-off. On a finite turing machine floating arithmetic is a motherfucker

The above theorem is a non-starter basically. In this universe 0.999999999999........ = 1
Scott Mayers
Posts: 1692
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

@logik

Cool.

The author of the book, "Essential Turing", does a pretty good intro updated and explained to each of Turing's papers before presenting them. Another I like that ties all these together in a clever way combining music, art, and logic in a very descriptive and indepth way is Douglas R. Hofstdter's, "Godel, Escher, Bach: An Eternal Golden Braid". He makes some minor errors in some examples but overall is an excellent read. ...though something you have to read in tidbits and move back and forth through some chapters to be sure you understand him. I have Godel's actual paper but still find it awkward to study without knowing the specific language and style he originally wrote in. The symbols and language throws you off and the context as it relates to Bertrand Russel's work requires too much reading to cover fairly. [Each of Bertrand's volumes on the 'Principia' average 1000 pages for each of the three. Godel actually is literally one of the very few (maybe 3 people?) who has ever fully read it completely before challenging it in his own works.

See the wikipedia entry on his works: https://en.wikipedia.org/wiki/Principia_Mathematica The original volumes are too expensive to reprint but there is a public source for pdf free print of all three volumes. But you'd also require his prior books to get a good sense of his approach.

I prefer Turing to understand it as well as the many computer logic and architecture books that help you understand the precise depth. It's easier to visualize and enable it to be conceptualized better, especially for coders.
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Godel, Escher, Bach is on my bedside table as we speak Must have read it 10 times.

I have said it a few times before, but I see logic/computation as a huge LEGO set. You build models with it.
Input/output and that's all there is to it.

Build what ye will. And because I have been building stuff for 20 years, and I have had the opportunity/privilege to work on some really big systems I have intuitions that no paper or book can convey.

Failure - the great teacher!

Having recently made a turn past academia again, it surprises me how much these "Computer Science Professors" don't know!

Theory/practice....
Scott Mayers
Posts: 1692
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

Logik wrote: Fri Mar 01, 2019 11:47 pm Godel, Escher, Bach is on my bedside table as we speak Must have read it 10 times.

I have said it a few times before, but I see logic/computation as a huge LEGO set. You build models with it.
Input/output and that's all there is to it.

Build what ye will. And because I have been building stuff for 20 years, and I have had the opportunity/privilege to work on some really big systems I have intuitions that no paper or book can convey.

Failure - the great teacher!

Having recently made a turn past academia again, it surprises me how much these "Computer Science Professors" don't know!

Theory/practice....
Yes. I found this true too.

I have friends in my local university and intellectual discussion groups with many different backgrounds and the I get the same impression. There is just way too much information for any one specialist to deal with given the whole spectra of the subject with a tendency to more and more summarized (and rushed) courses. That's the top-down and 'abstraction layer' approach needed today to at least get people working without an extra 20 years to cover it all.

As for computer scientists in particular, whom I relate best, they too often rely on me more to lead the discussions with depth on these matters. I have the free time they don't. Depending on their particular country of origin or university, the emphasis in training differs too. And fewer begin as self-motivated learners. But the computer scientists are generally more logical than even many areas of science! [I had to explain to a grad student how constant velocity in a circle is an acceleration towards the center! This is elementary but the pressure on students doesn't favor the time needed to let it all sink in when they are forced to be lead rather than to learn at their own pace.

As for professors, some don't like their jobs more often than not. Teaching isn't always as appreciative when you can't work one on one and the nature of it outside of that appeal has to be to the creativity of presentation, more of an artistic aptitude than anything. And the money isn't that great either.