Monday, August 31, 2020

Digest for comp.lang.c++@googlegroups.com - 22 updates in 4 topics

olcott <NoOne@NoWhere.com>: Aug 30 08:35PM -0500

On 8/30/2020 6:23 PM, Mike Terry wrote:
> system addressed through arbitrary long URLs.  (Ok, maybe URLs have a
> max length, but we can envisage some new storage device addressed
> through IO subsystem not having this restriction.
 
I only really need to know about computations that are TM equivalent:
meaning for example a computation performed by a "C" or x86 machine
language program that executed on an input will derive equivalent output
to a Turing machine on equivalent input.
 
> thousands of posts so we'll see how it goes in this newsgroup.
 
> Regards,
> Mike.
 
I was just having this exact same idea. This means that a single feature
that I added to my x86-UTM environment makes this environment Turing
Complete for any computation that fits within its memory 32-bit memory
space: u32* Allocate(u32 Size);
 
 
--
Copyright 2020 Pete Olcott
olcott <NoOne@NoWhere.com>: Aug 30 09:35PM -0500

On 8/30/2020 8:30 PM, Ben Bacarisse wrote:
 
> Note "may". In the end it is likely to come down to how one chooses to
> interpret the standard. It's really not a clear-cut question. (See my
> reply to Mike Terry about that.)
 
On 8/30/2020 6:23 PM, Mike Terry wrote:
> design or language considerations,
 
> Regards,
> Mike.
 
So Kaz spurred an idea in you that spurred an idea in Mike that seems to
complete the circle. If Mike is right then any computation performed
within the 32-bit 4GB address space of the x86 architecture that
terminates normally would be equivalent to a computation on a Turing
Machine having equivalent input. Since the x86 machine language program
was generated by a "C" compiler then the "C" version of the program is a
Turing equivalent computation.
 
As long as this reasoning is completely correct this part of the
analysis is finished. Every computation by a "C" language program on an
input that terminates normally is equivalent to the computation on a
Turing on equivalent input.
 
Here is where the analysis gets extended:
The input to the halt decider is the x86 machine language of itself.
This means that the input to the Turing machine must be this same
algorithm implemented as a conventional five-Tuple Turing machine.
 
Since the task of making a "C" to conventional five-tuple Turing Machine
translator is very difficult we define an some augmentations that create
a virtual machine language that is Turing equivalent that "C" maps to
much more directly.
 
When this virtual machine executes a halt decider that takes its own
virtual machine description as its input then we can know by proxy that
the x86 halt decider has equivalent input to an actual Turing machine.
 
The input to the x86 based UTM derives equivalent output to the output
of a virtual machine that is equivalent to a Turing machine and has
input equivalent to the input to the x86 based UTM.
 
This proves (by proxy) that input to an actual Turing machine that is
equivalent to the input to the x86 UTM would derive equivalent output
from the actual Turing machine.
 
--
Copyright 2020 Pete Olcott
olcott <NoOne@NoWhere.com>: Aug 30 11:55PM -0500

On 8/30/2020 9:35 PM, olcott wrote:
> > design or language considerations,
 
> > Regards,
> > Mike.
 
If we assume that Mike's analysis is correct then we can conclude that
every x86 program that derives a result has an equivalent Turing machine
computation on equivalent input deriving an equivalent result.
 
If an x86 based halt decider derives a correct halting decision on the
basis of its own x86 code then there exists an equivalent Turing machine
(using the same algorithm) that correctly decides halting on its own
Turing machine description.
 
Now if we just had some computer science to back that up.
 
--
Copyright 2020 Pete Olcott
olcott <NoOne@NoWhere.com>: Aug 31 09:59AM -0500

On 8/30/2020 8:24 PM, Ben Bacarisse wrote:
 
> Yes, you can switch larger integer indexes for larger pointers. The two
> views are interchangeable. (Or have I missed the point you are
> making?).
 
If we had pointer names that were handled under-the-covers by a Turing
equivalent process then we could still have the essence of "C" on an
abstract machine with unlimited memory. This is not much more than a
paraphrase of what Kaz already said. The difference is that we switched
the context from the stack to the heap.
 
I think that I just figured out how to make at least one linked list of
truly unlimited length. It depends on unlimited length integers. To
explain this system I would use 1024-bit addressing that could be scaled
upward at any point in time.
 
2^1024 (1.797693134862315907729305190789e+308) bytes of RAM
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216
 
Here is the maximum address value in hex:
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
 
Implementing such a system on actual hardware requires some sort of
relative addressing. Using every single atom in the whole universe to
encode one single binary digit each would provide a woefully deficient
amount of RAM for 1024-bit addressing:
 
...it is estimated that the there are between 10^78 to 10^82 atoms in
the known, observable universe...
https://www.universetoday.com/36302/atoms-in-the-universe/#
 
The key thing about this memory system is that because it has no
theoretical limit to its scalability every Turing equivalent machine
tied to this abstract memory system that can be implemented in actual
hardware would be computationally identical to its abstract machine
version until the concrete machine reached its memory limit.
 
This provides a way to empirically test many theory of computation
problems.
 
--
Copyright 2020 Pete Olcott
Keith Thompson <Keith.S.Thompson+u@gmail.com>: Aug 31 11:18AM -0700

> to an abstract model of computation that is equivalent to a Turing
> machine in such a way that any Turing complete computation can be
> written in the "C" programming language.
[...]
 
I encourage anyone in comp.lang.c or comp.lang.c++ who wants to
reply to these posts to take a look at comp.theory, which has been
dominated by these arguments for years.
 
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */
Jorgen Grahn <grahn+nntp@snipabacken.se>: Aug 31 09:34PM

["Followup-To:" header set to comp.lang.c.]
 
On Mon, 2020-08-31, Keith Thompson wrote:
 
> I encourage anyone in comp.lang.c or comp.lang.c++ who wants to
> reply to these posts to take a look at comp.theory, which has been
> dominated by these arguments for years.
 
Ugh. I took a look and now wish I hadn't.
 
(Not that it seemed toxic or anything; it was just a very depressing
ghost of a newsgroup.)
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
boltar@nuttyella.co.uk: Aug 31 08:54AM

On Sun, 30 Aug 2020 21:59:12 +0200
>nowhere close to state of the art of low power consumption. A
>Cortex-M0+ device (32-bit) will use much less power than a PIC or an
>8051 for the same task.
 
Lets see some figures then because I find that very hard to believe
particularly if the PIC is operating in wake-on-interrupt mode.
David Brown <david.brown@hesbynett.no>: Aug 31 11:33AM +0200

>> 8051 for the same task.
 
> Lets see some figures then because I find that very hard to believe
> particularly if the PIC is operating in wake-on-interrupt mode.
 
Look them up yourself - the details all depend on exactly what you want
the system to do. But here's a hint for you - the current consumption
of the core during the deepest sleep modes is almost completely
irrelevant in most battery powered devices.
 
Or if you want proper help with embedded design, find someone who is
willing to spoon-feed you and who also has more than your own "did a few
courses twenty years ago with a single microcontroller" experience.
 
Finding things "hard to believe" just because they are outside your own
experiences seems to be a pattern for you. It does not encourage others
to help you. You appear to be convinced that your very narrow and badly
outdated thoughts on embedded development are all there is to know of
the field - so there is little point in giving you advice or information.
 
If you wake up one day and realise that perhaps you don't know
everything, maybe you can ask some questions and learn something.
boltar@nowhere.co.uk: Aug 31 09:37AM

On Mon, 31 Aug 2020 11:33:57 +0200
>the field - so there is little point in giving you advice or information.
 
>If you wake up one day and realise that perhaps you don't know
>everything, maybe you can ask some questions and learn something.
 
Translation: "Err, sorry, I can't provide those figures but I'll will provide
a load of self righteous bluster in its place and hope you go away".
David Brown <david.brown@hesbynett.no>: Aug 31 12:11PM +0200

>> everything, maybe you can ask some questions and learn something.
 
> Translation: "Err, sorry, I can't provide those figures but I'll will provide
> a load of self righteous bluster in its place and hope you go away".
 
I certainly could provide figures. I could point you to a Cortex-M4
microcontroller with 20 nA sleep modes. I could point you to designs
with code written in C++ that don't have batteries at all, but get
enough energy from the user walking around. But what does that help you
or anyone else?
boltar@nowhere.co.uk: Aug 31 03:43PM

On Mon, 31 Aug 2020 12:11:10 +0200
 
>> a load of self righteous bluster in its place and hope you go away".
 
>I certainly could provide figures. I could point you to a Cortex-M4
>microcontroller with 20 nA sleep modes. I could point you to designs
 
Yes, 20nA, very good. However not as good as these 8 bit PIC:
 
http://www.farnell.com/datasheets/1523199.pdf
 
"PIC microcontrollers with XLP technology feature the world's lowest active an
d
sleep power consumption"
 
"Active currents down to 50 μA/MHz
Sleep current as low as 9 nA
Battery lifetime > 20 years"
 
Chew on that.
David Brown <david.brown@hesbynett.no>: Aug 31 10:50PM +0200

> Sleep current as low as 9 nA
> Battery lifetime > 20 years"
 
> Chew on that.
 
You missed the bit where I pointed out how utterly useless these figures
are. If you knew the first thing about what you were doing, you'd
understand that already.
Terje Mathisen <terje.mathisen@tmsw.no>: Aug 31 07:50AM +0200

Juha Nieminen wrote:
>> Thats not the kind of jerkiness I was talking about which if you had half
>> a working braincell you'd have understood.
 
> Notice how you are the only one here throwing insults at people.
 
:-(
 
> I wonder why that is.
 
To all the people here "discussing" needed frame rates etc.: Please take
a look at one or more of Michael Abrash' keynote presentations during
Oculus Connect!
 
They have done a _lot_ of research into this over the last short decade,
you can start at the 2014 video:
 
https://www.youtube.com/watch?v=knQSRTApNcs
 
or go directly to one of the later which shows what they figured out in
the meantime.
 
In order to avoid visual artifacts which destroy the AR/VR experience,
they have to get a serious amount of processing done in a very short
timeframe.
 
Terje
 
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
Juha Nieminen <nospam@thanks.invalid>: Aug 31 06:45AM

> To all the people here "discussing" needed frame rates etc.: Please take
> a look at one or more of Michael Abrash' keynote presentations during
> Oculus Connect!
 
That's a good example. If it were indeed true that people can't distinguish
anything beyond something like 24 (or 25, or 30) frames per second, then
it shouldn't matter if a VR headset updates at eg. 30 Hz. That would
certainly be beneficial since even lower-end PCs would be able to handle it.
 
Yet, something like 80-90 Hz refresh rate is required so that the refresh
rate itself doesn't contribute to nausea. Quite clearly people can distinguish
between even 60 Hz and 80 Hz.
boltar@nuttyella.co.uk: Aug 31 08:51AM

On Sun, 30 Aug 2020 17:11:07 +0000 (UTC)
>> a working braincell you'd have understood.
 
>Notice how you are the only one here throwing insults at people.
 
>I wonder why that is.
 
Because I get tired of arguing the toss with someone who doesn't understand
the point despite me being very clear about it. Did you seriously think when
I mentioned jerkiness in HIGH DEFINITION video it had anything to do with
frame rate in 2020?? Try engaging your brain first next time.
boltar@nuttyella.co.uk: Aug 31 08:53AM

On Sun, 30 Aug 2020 11:01:58 -0700 (PDT)
 
>> I wonder why that is.
 
>People who try to pointlessly insult or belittle others do it usually
>because of inferiority complex and a lack of self-respect.
 
Thanks for your valuable insights there Yoda. Any more wisdom you can bless
us with from your Dummies Guide to Psychology book?
Juha Nieminen <nospam@thanks.invalid>: Aug 31 12:15PM

> the point despite me being very clear about it. Did you seriously think when
> I mentioned jerkiness in HIGH DEFINITION video it had anything to do with
> frame rate in 2020?? Try engaging your brain first next time.
 
No, what you are doing is trying to deflect and move goalposts, in order to
not have to admit having made a mistake.
 
Your original claim, which started the framerate discussion, was that it's
useless for video games to go above 3 Hz refresh rates because humans can't
distinguish anything higher. That game developers aiming at higher
framerates is just them trying to show off.
 
Now you are talking about some "high definition video", as if it had anything
at all to do with your original assertion (which was about game framerates,
absolutely nothing to do with video codecs).
boltar@nowhere.co.uk: Aug 31 03:35PM

On Mon, 31 Aug 2020 12:15:09 +0000 (UTC)
>useless for video games to go above 3 Hz refresh rates because humans can't
>distinguish anything higher. That game developers aiming at higher
>framerates is just them trying to show off.
 
2 entirely different threads which you've clearly got mixed up in your head
because A) you're an idiot or B) you're just looking for an argument. Here's
my original post:
 
--------------
From: boltar@nuttyella.co.uk
Subject: Re: Are there any asm-instructions to support OOP
Message-ID: <rib6af$1kuh$1@gioia.aioe.org>
 
On Fri, 28 Aug 2020 10:34:17 -0400
Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>when the individual images are "perfectly" crisp (as is typically the
>case in sports on TV where it's recorded at higher rates to be able to
>replay in slow motion IIUC).
 
A current problem with video streams is the compression algorithm not being
able to keep up with fast motion or panning and introducing a noticable
jerkiness to the output. This only seem to happen on HD so possibly its an
artifact of H264 because SD streams just used to break up into blocks.
--------------
olcott <NoOne@NoWhere.com>: Aug 30 07:17PM -0500

On 8/30/2020 6:23 PM, Andy Walker wrote:
>> equivalent.
 
>     You don't know that the machines are going to fail to halt,
> in general.  Halting problem.  You don't know how long to wait to
 
Yes that is why a refutation of the conventional self-referential
halting problem proofs would be significant.
 
> you know that both machines halt, *then* you can find out whether
> they are equivalent.  If the machines are equivalent on some input,
> you don't know whether they are equivalent on other inputs.  Since
 
That two machines always derive equivalent output from equivalent input
and fail to halt on the same inputs proves that these two machines are
equivalent.
 
We may also know that two machines are equivalent on all inputs if each
machine can simulate the other.
 
> completely inscrutable, in general, given arbitrary data.
 
>     If you want to know things about programs, then you have to
> write them in such a way that theorems about them can be proved.
 
I only need to prove that certain computations that halt on specific
inputs are equivalent to a Turing machine on equivalent input.
 
My whole goal here is to prove that a halt decider written in "C" that
analyzes the x86 machine language of itself could be directly applied to
Turing machines.
 
> Then you may be able to say interesting things about programs that
> conform to your specification.  Otherwise the future is somewhat
> bleak.
 
Any virtual machine that implements an abstract model of computation
that is provably Turing equivalent will have identical computation to
any concrete hardware implementation of this abstract model until a
computation on this concrete model requires more RAM than it has.
 
In simpler words a program written in the virtual machine language will
run exactly the same (identical execution trace) on the abstract machine
as the concrete machine unless and until the concrete machine runs out
of RAM.
 
If we did not hit the RAM limit then we know that the execution of the
program on concrete machine would be equivalent to executing an
equivalent program on an actual Turing machine.
 
Every "C" language program that can be translated into the machine
language of any virtual machine that is provably Turing equivalent would
derive equivalent output to equivalent input on an actual Turing machine.
 
This establishes the basis of the line-of-reasoning showing that my
intuition that "C" programs always have been equivalent to Turing
machines is probably correct.
 
The above possibly creates a new term-of-the-art of computer science, a
Turing equivalent computation:
 
A Turing equivalent computation is any computation that can be
translated into the machine language of any virtual machine that is
provably Turing equivalent.
 
 
--
Copyright 2020 Pete Olcott
Richard Damon <Richard@Damon-Family.org>: Aug 30 08:43PM -0400

On 8/30/20 4:19 PM, olcott wrote:
 
> Or we could construe not halting as an empty set of output. As long as
> the two machines produced equivalent output when they halted or failed
> to halt on equivalent input the two machines are black box equivalent.
 
But just because we haven't halted YET, doesn't mean that if we wait
some arbitrary period of time more that neither of them might halt. Any
definition based on comparing the outputs at some finite time is
incomplete, and possibly inaccurate.
olcott <NoOne@NoWhere.com>: Aug 30 08:21PM -0500

On 8/30/2020 7:43 PM, Richard Damon wrote:
> some arbitrary period of time more that neither of them might halt. Any
> definition based on comparing the outputs at some finite time is
> incomplete, and possibly inaccurate.
 
On the other hand any definition based on comparing the results after
both machines have halted would be correct for the computations that
result in halting.
 
--
Copyright 2020 Pete Olcott
olcott <NoOne@NoWhere.com>: Aug 31 08:47AM -0500

On 8/31/2020 3:59 AM, Andy Walker wrote:
 
>> That two machines always derive equivalent output from equivalent
>> input and fail to halt on the same inputs proves that these two
>> machines are equivalent.
 
That is why you have to read everything that I said and not merely
glance at a few word before forming you rebuttal.
 
On 8/30/2020 7:17 PM, olcott wrote:
> We may also know that two machines are equivalent on all
> inputs if each machine can simulate the other.
 
The easy way to know that a machine is Turing equivalent is to start
with a Turing machine and then only add features to this exact same
model of computation that make it easier to work with and not have more
computational power. If you mess up and add computational power then
this "mistake" refutes Church-Turing.
 
>     It would, but there is no effective general method to show
> that.  You're going round in circles.  But we knew that.
 
You ignored the way to show that reiterated above.
 
--
Copyright 2020 Pete Olcott
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)