Pure functions? What the heck are those ?!?!

[Skepdick]

I have no idea what your point is, and I would honestly be surprised if anybody but you does at this point.

The point is the semantic/conceptual distinction between these two functions.

A distinction which Mathematics cannot account for and empiricists can!

Code: Select all

def f():
	5+5 //Do some computation and return nothing

Code: Select all

def g():
	pass // Do nothing

A Mathematician will tell you f ≡ g.
A empiricist will tell you f does more work than g - f requires more resources than g

The point is that Programming languages are founded upon Linear Logic (which can talk about resource-boundedness, duality, interaction etc.) so there's a way to account for the interaction between me-the-observer and the function that I am observing. Think senders (of input), receivers (of output), network protocols (transporting input and output messages).

And Mathematics can't even acknowledge that there exist such things as Mathematicians in the domain of discourse.

[PeteOlcott]

Mathematicians keep talking about "pure" functions.

I wonder if you could name them. I've never heard the term used in math, only in computer science. Never in math, not once. Can you name any of these mathematicians who "keep talking" about something that there is zero evidence they're talking about?

A pure function is a function that has no external input and no external output (no side-effects). What incoherent nonsense is this?

It's your understanding that's incoherent. According to Wiki, a pure function is " a function that has the following properties:[1][2]

The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams).
The function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams)."

There's no restriction on external input or output. On the contrary, any function must receive some input (even if null) and must return some output value, even if null. You are misunderstanding side effects.

A pure function in Python3 would be

Code: Select all

def pure_squarer(x) : 
    return x * x

It always returns the same output for the same input, and has no external or side effects.

An Input is the universe affecting the function.
An output is the function affecting the universe.

Please read the Wiki page on pure functions. Every function takes an input and returns an output. A pure function does so without creating side effects, and without relying on anything outside the function to determine the output.

For example a non-pure function would be

Code: Select all

import datetime()
def not_pure :
    return datetime.datetime.now()

As you can see, the function returns a different value each time it's called, and depends on the time of day.

Inputs/Outputs ARE side-effects!

For gosh sakes, man. That's nonsense.

If we use Python as a model of computation this is a pure function, but it does nothing:

Code: Select all

   def f(): pass # Mathematical equivalent unknown 

The only way you could have a pure function by your definition is that if it does nothing. Obviously that's wrong.

This is NOT a pure function. It has outputs.

Code: Select all

   def g(): return 1 #Mathematical equivalent f() = 1 

That's a pure function. Always returns the same on the same input, no reliance on external state, no side effects.

This is NOT a pure function. It mandates input.

Code: Select all

   def h(x): pass # Mathematical equivalent unknown 

That's pathetic. How do you manage to have such wrong ideas? That's a pure function.

This is NOT a pure function - it mandates input and produces output:

Code: Select all

   def j(x): return x. # Mathematical equivalent f(x) = x 

That's a classic example of a pure function.

This is a pure function. It calculates the answer to 2+2, but doesn't give you the answer.

Code: Select all

   def k(): 2+2 # Mathematical equivalent unknown 

Then it's absolutely useless. Surely you can see that nobody would bother to invent a concept like pure functions if they were no-ops.

If one takes an extensional view of functions, thereare no such things as pure functions!

So wrong. Read the Wiki page. Read a book.

Mathematicians, do you even know what you are talking about when you talk about "pure functions"?

I have never seen a mathematician talk about pure functions. Pure functions are part of computer science. Of course if you call computer science a branch of math, as some do, then mathematicians talk about pure functions: namely, those mathematicians who are computer scientists.

I expect the usual incoherent insults in reply. Go.

Very important in computer science because impure functions are not Turing computable thus not covered by the Church-Turing thesis.

[Skepdick]

Very important in computer science because impure functions are not Turing computable thus not covered by the Church-Turing thesis.

Then don't use that model of computation!

Use an effect system like EFF.

It's 2022, not 1939 for fucks's sake!

[wtf]

Very important in computer science because impure functions are not Turing computable thus not covered by the Church-Turing thesis.

Everything physical computers do is Turing computable. How could it be otherwise? Since programmers routinely write functions with side effects, those functions must necessarily be Turing computable. You are making a pretty wild statement that working programmers routinely write code that is not Turing computable.

Nice use of fonts though. Makes your words much more impressive.

[Skepdick]

Everything physical computers do is Turing computable. How could it be otherwise?

I have absolutely no idea how to implement a timeout operator on a Turing machine.

I think that is the simplest example of an Oracle being necessary.

[wtf]

I have absolutely no idea how to implement a timeout operator on a Turing machine.

I think that is the simplest example of an Oracle being necessary.

The program registers a timer with the OS. The OS puts it on a list of timer events and checks the list every so-many clock cycles, and times out any operation that's on the list that's timed out. I may have the details wrong but the basic idea is right. This isn't rocket surgery.

Are you claiming that oracles -- conceptual entities that can solve the Halting problem -- are installed in every consumer laptop that comes off the assembly line? I don't believe you.

[Skepdick]

The program registers a timer with the OS. The OS puts it on a list of timer events and checks the list every so-many clock cycles, and times out any operation that's on the list that's timed out. I may have the details wrong but the basic idea is right. This isn't rocket surgery.

You are not hearing me. I know how it works in practice. I don't know how to implement the operator in the computational model of a Turing machine because a Turing machine doesn't have an clock or interrupts.

Interrupts are like side-effects (undeclared outputs) except they are inputs to the function. Parameters passed after the original invocation.

Are you claiming that oracles -- conceptual entities that can solve the Halting problem -- are installed in every consumer laptop that comes off the assembly line? I don't believe you.

Sure. Every modern computer is networked to an Oracle - the user. Every program halts when I turn it off; or when I run it with timeout()

[wtf]

You are not hearing me. I know how it works in practice. I don't know how to implement the operator in the computational model of a Turing machine because a Turing machine doesn't have an clock or interrupts.

Interrupts are implemented by an algorithm. Any computer is a physical instantiation of a TM. I don't know exactly how a real life computer is implemented as a TM but I assume it can be done.

Sure. Every modern computer is networked to an Oracle - the user.

You are claiming that humans know how to solve the Halting problem? Revolutionary news if true, since that would immediately falsify all computational theories of existence and mind.

Also FWIW Oracle is a database and enterprise software corporation. A small-o oracle is a thing in computer science.

[Skepdick]

Interrupts are implemented by an algorithm.

Interrupt handlers are implemented by an algorhtm. Interrupts are unspecified inputs to a function - they are a source of non-determinism into the function.

An interrupt event may never arrive.

Any computer is a physical instantiation of a TM. I don't know exactly how a real life computer is implemented as a TM but I assume it can be done.

Well, yes if you believe that the theory is complete. Which is precisely why I went for the jugular.

Networking/communication/interrupts are the equivalent of two Turing machines interacting. That's a whole different paradigm to the usual Mathematical reductionism. The whole is greater than the sum of its parts.

You are claiming that humans know how to solve the Halting problem? Revolutionary news if true, since that would immediately falsify all computational theories of existence and mind.

*yawn* There is no general solution but that's a theoretical concern. I am talking about all of the implications of Rice's theorem.

All non-trivial semantic properties of computer programs are undecidable by Turing machines. Some non-trivial semantic properties are obviously decidable by humans and if I can decide something "undecidable" and communicate the answer to my "Turing machine" then the combination of me+my computer is a more powerful a computational system than a Turing machine alone. Humans are oracles that can't solve all decision problems, but they can solve more decision problems than a Turing machine.

Will this Bash code halt? That's undecidable, but I am pretty sure it will halt if it receives a termination signal! Will it receive a termination signal? That's undecidable, but I know it will.

Code: Select all

#!/bin/bash -l
function interrupt_handler(){
	echo "I've been told to halt!"
}

trap interrupt_handler EXIT

echo "My PID is $$ - lets go!"
while true;
do
	sleep 0.5
done

Also FWIW Oracle is a database and enterprise software corporation. A small-o oracle is a thing in computer science.

Well, look at you! Showing off your error-detection and error-correction algorithm in practice!

[wtf]

Interrupt handlers are implemented by an algorhtm.

Hence Turing computable. Glad we agree on that. I noticed you slipping into your usual lack of civility a couple of times so I'll let you go. Maybe it's just your style.

[Skepdick]

Hence Turing computable.

Hence an irrelevant red herring. Why are you conflating interrupts and an interrupt handlers?

You can implement an interrupt handler on a Turing machine.
You cannot implement an interrupt on a Turing machine.

Where would the signal come from? Turing machines don't have any IO.

The moment we are dealing with signaling and interaction between processes we are in the domain of process calculi, not Turing machines.

Glad we agree on that.

We do? Nobody told me.

I noticed you slipping into your usual lack of civility a couple of times so I'll let you go. Maybe it's just your style.

Yeah... I notice a pattern of using my intolerance of your obscuratism as an excuse to exit. Maybe obscurantism is just your style?

[Skepdick]

Very important in computer science because impure functions are not Turing computable thus not covered by the Church-Turing thesis.

It's going to be very difficult, if not impossible to explain to you that your "simulating halting decider" is an impure function.

It allows for external signaling/interruption. It's not a Turing machine, and so it's not subject to the implications of the Church-Turing thesis.

[wtf]

Hence an irrelevant red herring. Why are you conflating interrupts and an interrupt handlers?

What? The handler is a block of code executed by the OS on behalf of the interrupt. They go together like ham on rye.

You can implement an interrupt handler on a Turing machine.
You cannot implement an interrupt on a Turing machine.

Ok I see the point you are making, but I don't agree. The handler is a block of code, so it's executable on a TM. But the interrupt itself is just a particular data location in a register on the cpu. A TM can emulate memory locations. In a working (physical) computer, the OS periodically checks the interrupt locations to see if any of them have been set; and if so, the corresponding handlers are invoked. Surely you know that. So I don't see why you think interrupts can't be implemented by a TM. It seems to me they can.

Where would the signal come from? Turing machines don't have any IO.

Not every interrupt comes from I/O. One of the executing processes can raise an interrupt. So these would be internally generated interrupts that could easily be implemented in a TM.

I see the distinction between TMs and what you're calling process calculi, and I recognize the distinction and appreciate your drawing my attention to it. But even in a pure TM situation, an internal process could raise an interrupt just by setting the appropriate bit or simulated memory location.

The moment we are dealing with signaling and interaction between processes we are in the domain of process calculi, not Turing machines.

Ok. I read that web page and of course you are right that systems made up of interacting processes on different computers are not TMs. For example client/server systems, such as a web browser interacting with a web server, are not TMs.

However I followed some of the links in that article, and it's clear that process calculi have at most the computational power of TMs and no more. So if I'm using "TM" to mean any algorithmic computation whatsoever, you're correct that I'm using the term loosely. But if I mean to include process calculi as algorithmic computational systems, they have no more computational power than a TM; and that's the sense in which I'm using the term TM. I hope this is clear. You're right that I should use the more general term, but you are still not making your point, because process calculi have no more computational power than pure TMs.

That is to say, process calculi of any type do not break the Church-Turing thesis nor do they have any more computational power than TMs. So I don't see the point you are making, other than correcting my loose usage of TM to encompass any algorithmic process. Adding I/O operations or distributed processing doesn't break Church-Turing and can't compute anything a TM already can.

[Skepdick]

What? The handler is a block of code executed by the OS on behalf of the interrupt. They go together like ham on rye.

Yes, but that which triggers the OS to execute the interrupt handler is not the OS, or any process running on the OS.

In the event of timeouts it's the hardware clock. Which has its own, separate CPU. Its own logic - monotonically increasing function... (blah blah).

Ok I see the point you are making, but I don't agree. The handler is a block of code, so it's executable on a TM. But the interrupt itself is just a particular data location in a register on the cpu.

Yes sure. Lets pretend it's some 1-bit register. What it is doesn't matters. Who is allowed to toggle that register matters.

When that register is toggled by whatever it is toggled by - the CPU alters its control flow.

A TM can emulate memory locations. In a working (physical) computer, the OS periodically checks the interrupt locations to see if any of them have been set

Precisely. Set by who/what? What is mutating the Turing Machine's memory locations (tape) other than the Turing Machine itself?!?

Interrupts are shared memory - a communication channel between two separate programs.

Not every interrupt comes from I/O. One of the executing processes can raise an interrupt. So these would be internally generated interrupts that could easily be implemented in a TM.

Every interrupt IS I/O. Something (not you!) is mutating your memory!

I see the distinction between TMs and what you're calling process calculi, and I recognize the distinction and appreciate your drawing my attention to it. But even in a pure TM situation, an internal process could raise an interrupt just by setting the appropriate bit or simulated memory location.

Well, yes. That is how inter-process communication works.

The point you don't seem to be appreciating is that two distinct processes are sharing a single memory location - they have an open communication channel.

One process can pass messages to the other process by writing to their shared memory location.

Ok. I read that web page and of course you are right that systems made up of interacting processes on different computers are not TMs. For example client/server systems, such as a web browser interacting with a web server, are not TMs.

Yes. Any externally-interruptable process is not a TM.

However I followed some of the links in that article, and it's clear that process calculi have at most the computational power of TMs and no more.

Yes. That would be true IF the set of interracting processes were a closed system.

In practice each computer in the world is interacting with other computers AND with the humans using them. Humans drive interrupts. Keyboard, Mouse clicks...

So if the process calculi is equivalent to a TM then the process calculi is also an insufficient model to account for modern computation.

External interrupts render the system open and non-deterministic.

So if I'm using "TM" to mean any algorithmic computation whatsoever, you're correct that I'm using the term loosely. But if I mean to include process calculi as algorithmic computational systems, they have no more computational power than a TM; and that's the sense in which I'm using the term TM. I hope this is clear. You're right that I should use the more general term, but you are still not making your point, because process calculi have no more computational power than pure TMs.

Then I must be mistaken in the finer details. If the process calculi is deterministic then the process calculi is as inadequate in accounting for modern computers as turing machines are!

That is to say, process calculi of any type do not break the Church-Turing thesis nor do they have any more computational power than TMs. So I don't see the point you are making, other than correcting my loose usage of TM to encompass any algorithmic process.

Modern computers are non-deterministic. Turing machines are not like that!

[PeteOlcott]

Very important in computer science because impure functions are not Turing computable thus not covered by the Church-Turing thesis.

Everything physical computers do is Turing computable. How could it be otherwise? Since programmers routinely write functions with side effects, those functions must necessarily be Turing computable. You are making a pretty wild statement that working programmers routinely write code that is not Turing computable.

Nice use of fonts though. Makes your words much more impressive.

I hope that you are correct about that, others seem to disagree.
For example others seem to think that a C function that depends
on local static memory is not a computable function. I formerly
had your point of view on this for many decades.