graycat

As in one of volumes of Knuth's The Art of Computing, Heap sort is in place and achieves the Gleason bound so can be regarded as not beaten by quick sort.

What I wrote is correct but does not address the traditional Turing Machine halting problem or solve it.

The traditional halting problem is theoretical, i.e., not close to anything practical, and so is what I wrote.

And I did not claim that what I wrote is a contribution to "complexity theory".

The Turing Machine Halting Problem has long been standard computer science; from that it's common to conclude we can't tell if a program will stop. But that conclusion needs some theoretical assumptions, and my version is simpler and shows that we have to be careful drawing conclusions from the standard treatment.

Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem".

Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b).

> the law

Would be nice!!!

However, as is easy to see from recent, well known examples, the results of our legal system depend heavily on personal attitudes, predilections, and opinions of individual judges, lawyers, etc., and, net, "the law" is inconsistent, unpredictable, unreliable (some might say emotional and irrational), often too slow, too expensive, and a source not of justice or "the law" but of lawfare battles, war by special means. As in shooting wars, both sides lose. E.g., can see

Dershowitz to Newsmax: Boasberg Should Be Held in Contempt

at

https://www.newsmax.com/newsmax-tv/alan-dershowitz-james-boa...

where Judge Boasberg and Emeritus Harvard Law Professor Dershowitz strongly disagree.

For another example, one part of this Boasberg case had the SCOTUS rule 5-4 -- that is inconsistent and unpredictable.

In math, physical science, and now often in biology and medical science, we have many examples of one things, clear, explicit, highly predictable -- the Pythagorean theorem, Einstein's Special Relativity, protein folding, Phase III trials, placebo controlled, randomized, double blind.

But, in strong contrast, "the law" is unpredictable, in each case, no "one thing", closer to medieval ugly torture and nonsense than math, science, technology, etc. of 2025. The law profession should be ashamed. "Your Honor"? Not really.

As I understand the situation, the SCOTUS is created by our Constitution, but the rest of our legal system, including Judge Boasberg, is the creation of and funded by Congress. So, Congress can cut off the funds and maybe just abolish Boasberg's court.

My guess is that the media has raised attention, the voters want something better in our legal system, and soon Congress will make some changes. With also the POTUS, the legal system, "the law", currently widely less liked than a skunk at a garden party, can be turned inside out, fumigated, disinfected, bleached, scrubbed, washed, rinsed, hung out to dry, stitched, patched, ironed, folded, and used as, hmm, a seat cushion.

Sorry 'bout that. As a startup founder, my view is, at any or all costs, to stay low, quiet, out of sight, and anonymous, have only an LLC and never a corporation, and be far from any entanglements with "the law".

Stochastic process with the Markov property: Past and future are conditionally independent given the present. The general version of conditionally independent is from probability theory based on measure theory and the Radon-Nikodym theorem (with von Neumann's novel proof in Rudin, Real and Complex Analysis), but an easier introduction is in Erhan Çınlar, Introduction to Stochastic Processes.

In a Poisson process the time until the next event has the Poisson distribution and, thus, from a simple calculus manipulation, is a Markov process.

E.g., time from now until a molecule of hydrogen peroxide H2O2 decomposes to water and oxygen is independent of when it was made from water and oxygen. That is the basis of half life, the same distribution until decomposition starting now no matter when the chemical or particle was created.

In WWII, searching at sea, e.g., for enemy submarines, was important, and then was Bernard O. Koopman, Search and Screening, 1946 with an argument that time to an encounter between two ships had a Poisson distribution, i.e., was a Markov process.

In grad school, there was a question about how long US submarines would last in war at sea. Well, take n Red ships and m Blue ships with, for each ship, position, speed, and detection radius and, for each Red-Blue pair, given a detection, probabilities of Red dies, Blue dies, both die, neither die (right, these four have to be non-negative and add to 1). Now have specified a Markov process that can evaluate with a relatively simple Monte-Carlo simulation.

Had written a random number generator in assembler using an Oak Ridge formula, typed quickly, and did the simulation. Had a review by a famous probability prof and passed when explained how the law of large numbers applied. So, some pure and applied math and computing worked, but some politics didn't!

Computers and China? Hmm ....

For my next computer, e.g., for a Web server, considering an AMD processor, Gigabyte mother board, Western Digital disks (rotating and/or solid state), main memory, video display, etc.

Just checked, none of that comes from China!!! The businesses are in Taiwan, South Korea, the US. Manufacturing is in Taiwan, Thailand, Malaysia, South Korea. The processor design, the US. The equipment for manufacturing the chips, Holland.

So, for my startup, I'm happy!

For a smart phone -- not much interested.

> challenge would you tackle if resource was not a problem?

(1) Have a good marriage, children who do well, and "live happily ever after", a MUCH bigger challenge than I expected.

My experience is that a significant fraction of women just do NOT want anything like the standard marriage vows, e.g., would rather get alimony and then be an alcoholic cat lady.

My guess is that (a) long each woman lived in a small tribe all in one open (no partitions) house, maybe 20 yards wide, 60 yards long, half-pipe, that is, semi-circular arches for both the walls and ceiling, much like a WWII US Army Quonset hut except made of wood and straw, intended to keep in warmth and keep out weather and wild animals. There the women served needs of the tribe, got their security from the tribe, and were loyal to the tribe and (b) are now suffering from missing (a). I.e., the nuclear family is not natural and is held together, weakly, mostly only by the cash economy, jobs, ownership, etc.

(2) Achieve AGI, artificial general intelligence.

(3) World peace, prosperity, health, and happiness.

(4) Automation so that machines work and humans live good lives.

(5) Make sense out of quantum mechanics -- sorry, physics experts, sorry, but sorry, from reading the best there is on quantum mechanics, von Neumann, Griffiths, etc., to my mind from my math Ph.D., the math of quantum mechanics just does NOT make good sense.

We can start with the simple theorem of Fourier theory, the uncertainty principle, and then what physics does with it, e.g., claims that empty space can spontaneously erupt with energy. Uh, from Fourier, Riemann, Lebesgue, Rudin, the Fourier transform of 0 is 0 -- simple.

Also the claims of superposition make no sense, e.g., one electron can be in two places at once -- suddenly with twice the mass, charge, momentum, and energy? Add some more beam splitters and the electron can be in 64 places at once with 64 times as much mass, charge, momentum, and energy?

And have some clear technical writing, e.g., what are "quantum numbers"? Need definitions, explanations, examples, the usual in technical writing.

E.g., actually give what would be in the math of, say W. Rudin, an actual clear DEFINITION of a wave function as an actual function, with domain, range, etc. For each wave function, and d > 0, there are points x and y where the wave function is non-zero and the distance between x and y is greater than d?

(6) Make sense out of space, the vacuum, e.g., how it enforces conservation of energy, momentum, etc.

(7) Make sense out of the Big Bang.

(8) Do some stochastic process math to say how DNA makes evolution proceed at the speed it does.

(9) Finally make progress on P versus NP.

Okay, mostly use Windows 7 Professional (with 100+ "updates") for general purpose and software development but for such usage and/or a Web server what to get now? Windows 2xxx?

WOW! IPC, instructions per cycle? Sure, back in those days, usually how many cycles per instruction! The 360/91 was a high end thing, said to cost $13 million. One was at the Navy lab, JHU.APL. As I recall, it could do 1 floating point (32 or 64 bits?) instruction per cycle and sometimes 3 in 2 cycles.

> the entire world circa 1970.

About then was the IBM 360/91 with a 60 nanosecond cycle time. So, that would be a clock speed of

     1/ ( (60)/(10^9) ) 

     = (10^9) / 60

     = 10^7 (100 / 60 )

     = 10^7 (10 / 6 )

     = 10^7 (1.66)

     1.66 (10,000,000)

     16.66 (1,000,000)

     = 17 Mhz

Now we can have clock frequencies of 4 GHz, that is

     4000/17 = 235

times faster. And we can have 16 cores instead of 1 for

     (16)(4000) / 17 = ~4000

times faster. "entire world"?

One approach to, and reason, for college:

As in

     https://en.wikipedia.org/wiki/Medicine_show

in the 1800s in the US, there were lots of "Medicine Shows":

     "Medicine shows were touring acts
     (traveling by truck, horse, or wagon
     teams) that peddled "miracle cure"
     patent medicines and other products
     between various entertainments."
     

So, the audiences were getting lied to, manipulated, fooled, exploited, etc., wasting time and money and risking their health.

Currently with some of the media and more, it's the same for the audiences -- fooled.

Well, then: Have a college education with some math, physical science, biology, psychology, literature, fine arts, meet some people and improve understanding of people see some all time great examples of good thinking, and then will have some good defenses against being fooled.

E.g., there is from page 76 of

     Susan Milbrath, 'Star Gods of the
     Maya:  Astronomy in Art, Folklore,
     and Calendars (The Linda Schele
     Series in Maya and Pre-Columbian
     Studies)', ISBN-13 978-0292752269,
     University of Texas Press, 2000.

with

     "Indeed, blood sacrifice is required
     for the sun to move, according to
     Aztec cosmology (Durian 1971:179;
     Sahaguin 1950 - 1982, 7:8)."

(the old Google link is now broken), that is, the Maya concluded that it was important for the sun to keep moving across the sky and to ensure this would kill people and pour their blood on a rock.

Today with some good education, we can look at this claim and right away conclude: Absurd, nonsense, wasting human life.

So, the Mayan audiences didn't have a good, current US college education and were vulnerable to being seriously fooled.

For some of the college courses,

     "Once you have been in a 
     course like that about 
     all you can say is that 
     you have seen it."  

And experience shows that even just having "seen it" means have some good judgment about thinking, separating the good from the bad. So, it's common to say that a college education yields abilities in critical thinking.

Maybe PG is "superficial". Hmm ... It may be that commonly drilling down as deep as can is not productive and, instead, there is some wisdom that commonly productive solutions are surprisingly simplistic, i.e., "superficial"?

Do? Make money enough to support self and family and then have a good family.

Understand people. With all the talk in the news about the current Disney Snow White, got out the DVD for the old Disney Cinderella: Yup, have learned enough about people to see that the many plot events are not just incidental for the drama but examples of deep fundamentals about people. In particular understand what's important for good family formation.

Understand human societies, e.g., cultures, religions, economies, politics, war and peace.

Understand academics: E.g., a lot of academics that has done research that results in good tools to enable "Make good new things" has deep contempt for doing that.

Understand, say, math, physical science, biology, medical science, nature, technology, fine arts.

The US needs:

(1) To be strict and strong on illegal immigration.

(2) To be welcoming, courteous, gracious, flexible, understanding, and helpful otherwise.

In grad school, wrote a paper as a homework assignment for a course where reviewed a paper on the idea of using a minimium spanning tree for the traveling salesman problem. The paper did have some math addressing how close the idea was to optimality. That was a long time ago, and now don't have the reference or the homework! From a fast search, now there is

https://www.geeksforgeeks.org/approximate-solution-for-trave...

https://en.wikipedia.org/wiki/Minimum_spanning_tree

Am reminded that the nodes to be visited must have distances that obey the triangle inequality, e.g., like a plane.

Then when traversing the tree, when there is no arc in the tree to the next node, just leave the tree and go direct.

Your area may have several services that can keep you from being homeless. There should be some social workers good at helping people with just your problems. E.g., they may have a shelter you can use overnight. For long term housing, they may have an area, not easy to see from the main streets, with a few dozen manufactured/mobile houses with subsidized, low rents. They may have sources of food or money for food, maybe a free food credit card, and Walmart, etc. have selected basic foods for such payment means. Your area may have some essentially free basic health care -- apparently there are some quiet Federal programs that funnel money to pay for such services. Where I am, an immigrant started doing yard work mowing grass. Soon he had a truck pulling a trailer with equipment and had hired a few people. Now he has a very nice truck, trailer, and equipment -- big mower with 'sulky', leaf blowers, edge trimmers, etc., maybe > $150,000 in equipment. It looks like he is making good money, and he only works ~8 months a year. So, if could work for some such guy, could learn the details of his business and then start your own. Might help to read up a little on the botany of care and feeding of grass, flowers, trees. Shockingly, there may be more money in a grass mowing business than can expect as an employee with a BS in computer science: Such a business has some advantages, e.g., geographical barrier to entry. Get paid for the work, yes, but also for reliability, trust and generally pleasing the customers. Likely most of the candidate customers don't know much about competitive rates. In such small businesses, references stand to mean a lot. And if your area has cold winters, maybe could keep busy moving ice and snow. Tires for a car? Not so long ago, some people waited until the threads started to show! And might be able to get used tires for much less. Maybe some people for a while don't have licenses and insurance up to date. Maybe "Taxes? What taxes? I don't need no stink'n taxes!" Good luck!

> It's an approximation algorithm.

Clear. Nice. Thanks.

In that case, for the Traveling Salesman problem, build a minimum spanning tree and traverse that -- old result.

When Ada was first announced, I rushed to read about it -- sounded good. But so far, never had access to it.

So, now, after a long time, Ada is starting to catch on???

When Ada was first announced, back then, my favorite language was PL/I, mostly on CP67/CMS, i.e., IBM's first effort at interactive computing with a virtual machine on an IBM 360 instruction set. Wrote a little code to illustrate digital Fourier calculations, digital filtering, and power spectral estimation (statistics from the book by Blackman and Tukey). Showed the work to a Navy guy at the JHU/APL and, thus, got "sole source" on a bid for some such software. Later wrote some more PL/I to have 'compatible' replacements for three of the routines in the IBM SSP (scientific subroutine package) -- converted 2 from O(n^2) to O(n log(n)) and the third got better numerical accuracy from some Ford and Fulkerson work. Then wrote some code for the first fleet scheduling at FedEx -- the BOD had been worried that the scheduling would be too difficult, some equity funding was at stake, and my code satisfied the BOD, opened the funding, and saved FedEx. Later wrote some code that saved a big part of IBM's AI software YES/L1. Gee, liked PL/I!

When I started on the FedEx code, was still at Georgetown (teaching computing in the business school and working in the computer center) and in my appartment. So, called the local IBM office and ordered the PL/I Reference, Program Guide, and Execution Logic manuals. Soon they arrived, for free, via a local IBM sales rep highly curious why someone would want those manuals -- sign of something big?

Now? Microsoft's .NET. On Windows, why not??

> For a hobby project, what you describe is probably fine.

Thanks! Yup, it will be "a hobby project" until, if ever, it gets some users and revenue. Then, have several servers, some load balancing and redundancy, uninterruptible power with a generator outdoors on a concrete slab, contact Cloudflair or some such and have them do what is needed, etc.

Just looked up SSL, reverse proxies, firewalls, etc. Okay.

Asking: Okay, clearly there are a lot of people here with lots of experience running their software on cloud services from Microsoft, Amazon, Google, etc. Good.

But what about a solo founder running their Web site on a "full tower" computer they plugged together themselves?

So, why use a cloud server farm with its expense and complexity?

Or, get a mother board, a processor with 16 cores and a 4+ GHz clock, 128 GB of main memory, some rotating and/or solid state disks for a total of 20 TB or so, some external disks for backup, a recent copy of Windows Server, applications software from .NET, and a 1 Gbps Internet connection?? The computer -- tower case, power supply, motherboard, processor, disk, solid state disks, and Windows Server -- costs ~$3000?

So, a 1 Gbps Internet connection, ~$100 a month, would have capacity of, say, 100 MBps. If sending a Web page with 200 KB, then the peak capacity would be

     100 MBps / 200 KB = 500 pages/second.

Then 500 pages a second with 5 ads per page with revenue of, say, $2 per thousand ads sent (CPM), that would be

     500 * 5 * 2 / 1000 = $5/second

at peak capacity or maybe an average of half that for $2.50/second.

Then at 16 hours a day that would be revenue of

     2.50 * 60 * 16 * 30 = $72,000/month

For the electric power, at 200 W and $0.10/KWh, that would be

     200 * 24 * 30 * 0.10 / 1000 = $14.40/month

How many users?

With peak capacity of 500 pages a second and average of half that, 250 pages a second, for 16 hours a day, that would be

     250 * 60 * 16 * 30 = 7,200,000

pages a month. If on average send 5 pages per user, that would be

     7,200,000 / 5 = 1,440,000

users per month.

If users come on average 2 times a week that would be 8 times a month or

     1,440,000 / 8 = 180,000 users

from one tower case and some Web page software.

So, why use a cloud server farm with its expense and complexity?

Ah, my father in law was a farmer, grew wheat, corn, soy beans, but sometimes raised chickens. Along with the corn, when he fed the chickens anchovies from Chile he noticed rapid growth, called the little fish a growth factor.

Wellllll, long before his growth factor, we assumed we knew what a good balanced diet for chickens was. Then, presto, bingo, the issue was what barrels of fish, soy beans, ..., to feed the chickens to provide the diet for minimum cost. Right: Linear programming, the "diet problem", applied math in farming!

Own favorite source on stochastic calculus:

     Eugene Wong,
     {\it Stochastic Processes in Information and
     Dynamical Systems,\/}
     McGraw-Hill,
     New York,
     1971.\ \

> Grok 3 performs at a level comparable to, and in some cases even exceeding, models from more mature labs like OpenAI, Google DeepMind, and Anthropic. It tops all categories in the LMSys arena and the reasoning version shows strong results—o3-level—in math,....

"Math"? Fields Medal level? Tenure? Ph.D.? ... high school plane geometry???

As in

'Grok 3 AI and Some Plane Geometry'

at

https://news.ycombinator.com/item?id=43113949

Grok 3 failed at a plane geometry exercise.

Do remember some from when we were in Florida; since we moved to Tennessee when I was 5, those memories were from <= 5!

Memories:

(1) In a few seconds older brother taught me to ride a bicycle: He put me on his bicycle and held me up as I turned the pedals. He kept saying he was holding me up as I kept pedaling and he was > 10 feet back of me!

(2) Mom made eggnog! Last I ever had!

(3) Brother and I got 'twin' beds, with headboards, foot boards, and posts!

(4) Dad took a lantern, some dough balls, a net, and a big wash tub to the coast and returned with the tub full of shrimp!

(5) One baby sitter was really nice -- still remember her smile!

(6) Shela next door was my age, and we played. When her family moved to Milwaukee, I said "When I grow up I'm going to 'Wilwaukee' and marry Shela!"

> if nobody reads it?

Blog especially if no one reads it so that can learn how to blog so that people will read it!

"What a gift to give us to see ourselves as others see us?" -- Robert Burns.

"Price of land goes up": In simple terms, the Internet is providing huge areas of land suddenly now feasible for use; the larger supply will lower US average costs per acre.

How?

First have a clear statement of the context. Second, define and explain all the obscure terminology and mathematical notation -- at least give good references.

Gee, in one discussion of Lagrangians, saw "configuration space" and "constraints". Okay, studied topological spaces, vector spaces, inner product spaces, measure spaces, Banach spaces, Hilbert spaces, probability spaces, but never saw a definition or explanation of a "configuration space".

"Constraints"? Kuhn-Tucker optimization theory has a lot on constraints, for one of the issues there was a question, and I solved and published it. Thought I had some background in "constraints", but the Lagrangian explanations didn't make clear what they meant by "constraints".

A "symmetry generator"? This is the first I ever heard of any such thing although ugrad math honors paper was on group representations.

Then there was "phase space": What does that have to do with "phase" in light waves and sound waves? Sounds like one word with two different meanings?

E.g., "Poisson algebra": Okay, there is the Poisson stochastic process, e.g., seems to get assumed in "half-life" calculations, and with more in

Erhan \c Cinlar, {\it Introduction to Stochastic Processes,\/} ISBN 0-13-498089-1, Prentice-Hall, Englewood Cliffs, NJ, 1975.\ \

and there is abstract algebra, e.g., groups, rings, fields, ... But a "Poisson algebra"?

> The price of land will skyrocket

Is that really true?

Let's look at some data from Google, the World Bank, etc.:

     US land area: 3,532,316 square miles

     US population: 334.9 million

     640 acres per square mile

     ( 640 * 3,532,316 ) / 334,900,000 =
     6.750 acres per person

     Fertility rate: 1.66 births per woman
     (2022) World Bank

     GDP growth rate: 2.5% annual change
     (2023) World Bank

So, per family of four, that would be

     ( 4 * 640 * 3,532,316 ) / 334,900,000
     = 27 acres per family of four

"Skyrocket?" With the fertility rate of 1.66, the US population is falling so that the acres per person is increasing.

A guess is that people are crowded into tall buildings in dense cities to reduce costs of communications. So, yes, in dense cities, the cost of land per acre is comparatively high.

But the Internet is reducing the costs of communications meaning that people can move to land that is less densely populated and cheaper.

So, for the near future, tough to believe:

> The price of land will skyrocket

> I don’t have a good workflow and can’t even imagine one.

NOOOO problem. Simple solution. In one word, text. Two words, text editor. E.g., this Hacker News thread is at:

https://news.ycombinator.com/reply?id=42988455&goto=item%3Fi...

Sooooo, have that URL and the title of this thread in a simple, old-fashioned, file, text file, maintained with my favorite editor. Then, when want to revisit this thread, use the editor's excellent text search facilities to find the URL, and then, via a simple editor macro I wrote, one keystroke, and, bam, boom, have the Web page displayed via my pre-selected Web browser.

Text. Keep nearly everything important in just text. Source code of .NET for my startup's Web site? Text, never anything but text. Visual Studio? No thanks: Did I mention text? Posts at Hacker News? Text, both for my posts and those of everyone else. File system directory tree? Uh, again the T-word, with the tree from the Rexx function SysFileTree. In the editor, can sort on date, size, name, etc.

Random number generation?

There still is:

     R. R. Coveyou, R. D. MacPherson,
     "Fourier Analysis of Uniform Random
     Number Generators", Journal of the
     ACM, Volume 14, Issue 1, Jan. 1967,
     Pages 100-119.

From memory (might check the paper):

     i -- a positive integer
     ip1 -- a positive integer
     Set i = 1
     Do Forever
       Set ip1 = i * 5^15 + 1 mod 2^47
       Return(ip1)
       Set i = ip1
     End