At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
A further elaboration of this comes from the
notion of computable functions and Rice's
Theorem:
Turing machine deciders compute functions from
*finite string inputs* to {accept, reject} values
according to whether the input has a syntactic
property or specifies a semantic property.
Turing machine deciders only report on the behavior
of Turing machines indirectly through the proxy of
finite string inputs. *This key detail has been ignored*
At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
On 13/12/2025 16:44, olcott wrote:
At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
I continue to reject the use of "accept" and "reject" here. And I also
reject the use of "indicates" wrt to them.
There's no good reason to suppose this is about grammars and strings
rather than propositions about programs. To the extent that they might
be isomorphic you need to introduce the notion of grammars and string acceptance by them to give "accept" and "reject" and "indicates" the
correct meaning.
On 12/13/25 11:44 AM, olcott wrote:
At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
A further elaboration of this comes from the
notion of computable functions and Rice's
Theorem:
Turing machine deciders compute functions from
*finite string inputs* to {accept, reject} values
according to whether the input has a syntactic
property or specifies a semantic property.
Turing machine deciders only report on the behavior
of Turing machines indirectly through the proxy of
finite string inputs. *This key detail has been ignored*
So, if the function isn't "Computable", it is still a Function, but no Turing Machine (or equivalent) can compute it.
On 12/13/2025 1:14 PM, Richard Damon wrote:
On 12/13/25 11:44 AM, olcott wrote:
At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
A further elaboration of this comes from the
notion of computable functions and Rice's
Theorem:
Turing machine deciders compute functions from
*finite string inputs* to {accept, reject} values
according to whether the input has a syntactic
property or specifies a semantic property.
Turing machine deciders only report on the behavior
of Turing machines indirectly through the proxy of
finite string inputs. *This key detail has been ignored*
So, if the function isn't "Computable", it is still a Function, but no
Turing Machine (or equivalent) can compute it.
There seems to be no such thing as uncomputable
functions when Turing machines are construed
entirely in terms of finite string rewrite rules.
At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
A further elaboration of this comes from the
notion of computable functions and Rice's
Theorem:
Turing machine deciders compute functions from
*finite string inputs* to {accept, reject} values
according to whether the input has a syntactic
property or specifies a semantic property.
On 12/13/2025 1:33 PM, Tristan Wibberley wrote:
On 13/12/2025 16:44, olcott wrote:
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
I continue to reject the use of "accept" and "reject" here. And I also
reject the use of "indicates" wrt to them.
My goal is to have accepted definitions as my only basis.
This is a grammatically correct English sentence:
"flpm erf09-25k (*&j^*&NJ*&jkNef", reject.
On 14/12/2025 16:16, polcott wrote:
This is my first principle
All Turing machines only compute the mapping
from input finite strings to some value.
I maintain that's wrong. it should be "compute only".
You previously said it means the same either way around but that's not
true for "only" even if it's true for many adverbs because of a
syntactic ambiguity due to the many parts of speech "only" can fulfil.
[only compute] [the <something>]
[compute] [only the <something>]
the first can actually be wrong if nonterminating programs (ie, keep operating without making progress producing a result) are not said to compute, which I'm told they are not. Those turing machines do not
compute so it can't be that compute is the only thing they do.
That the only thing they compute is <something> could be true depending
on the <something>, which is another matter.
On 13/12/2025 18:44, olcott wrote:
At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
A further elaboration of this comes from the
notion of computable functions and Rice's
Theorem:
Turing machine deciders compute functions from
*finite string inputs* to {accept, reject} values
according to whether the input has a syntactic
property or specifies a semantic property.
Every property a Turing machine can compute is a syntactic property.
A Turing machine sees only its input. It does not see any neaning of
the input. Therefore it has no access to semantic properties. A
semantic property can be computed only if it is equivalent to a
syntactic property.
On 12/14/2025 4:43 AM, Mikko wrote:
On 13/12/2025 18:44, olcott wrote:
At the most fundamental level:
All Turing machines only compute the mapping
from input finite strings to some value.
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
A further elaboration of this comes from the
notion of computable functions and Rice's
Theorem:
Turing machine deciders compute functions from
*finite string inputs* to {accept, reject} values
according to whether the input has a syntactic
property or specifies a semantic property.
Every property a Turing machine can compute is a syntactic property.
A Turing machine sees only its input. It does not see any neaning of
the input. Therefore it has no access to semantic properties. A
semantic property can be computed only if it is equivalent to a
syntactic property.
If that was true then Rice's theorem would be
wrong before it even got started.
In computability theory, Rice's theorem states
that all non-trivial semantic properties of
programs are undecidable. A semantic property
is one about the program's behavior https://en.wikipedia.org/wiki/Rice%27s_theorem
The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except as noted in
the sig.
On 14/12/2025 16:16, polcott wrote:
On 12/14/2025 6:51 AM, Tristan Wibberley wrote:
On 13/12/2025 19:50, olcott wrote:
On 12/13/2025 1:33 PM, Tristan Wibberley wrote:
On 13/12/2025 16:44, olcott wrote:
Turing machine Deciders are a subset of this
where the value indicates accept or reject a
finite string by some criterion measure.
I continue to reject the use of "accept" and "reject" here. And I also >>>>> reject the use of "indicates" wrt to them.
My goal is to have accepted definitions as my only basis.
Oh! I just noticed it's a new statement with "by some criterion measure" >>> which makes it excellent. I retract my rejection.
Good.
This is my first post on the halting Problem
https://groups.google.com/g/sci.logic/c/V7wzVvx8IMw/m/ggPE6a-60cUJ
I worked for 15 years mostly on the basis of intuition.
Then 2 more years creating fully operational code. Then
3 years of discussing this code.
Now I am finally getting around to anchoring these
intuitions and my working code in standard definitions.
My current working code.
https://github.com/plolcott/x86utm/blob/master/Halt7.c
I had to refrain from learning the standard definitions
before now or they would have boxed me into the standard
views.
My insights are entirely from slight nuances of meaning
that are abstracted away in the standard definitions.
I had to carefully reverse-engineer the exact details
of what was actually happening before I could see what
nuances of meaning were being left out. Initially I
had to use my own non-standard terminology to do this.
This is my first principle
All Turing machines only compute the mapping
from input finite strings to some value.
My second correction of three that are needed (I will return to the
third later once I've thought more):
"value" is not defined, a first principle must be elementary (introduces terms of art but does not depend on them).
Here are two alternatives to illuminate the matter, but I think they're
not good enough:
1st alternative: You need a prior principle defining "value". That's not entirely intuitive though we pretend it is, like so much that you
correctly find to be a problem.
2nd alternative: All Automatic Turing Machines compute only an output
finite string from an input finite string.
They're wrong because a turing machine has a state (m-configuration),
whose change--and given a constant initial state then also itself--is,
in effect, computed.
The 3rd alternative is contingent as noted, a contingency whose premise
I think you suppose:
3rd alternative, admissible when considering an ATM to be a physical
machine rather than a mere formal system: An Automatic Turing Machine is
one of those things restricted--at least in part--such that
it computes
nothing more than an output finite string along with its own halting
state from an input finite string along with its own pre-nominated
initial state.
| Sysop: | DaiTengu |
|---|---|
| Location: | Appleton, WI |
| Users: | 1,090 |
| Nodes: | 10 (0 / 10) |
| Uptime: | 198:22:00 |
| Calls: | 13,924 |
| Calls today: | 1 |
| Files: | 187,024 |
| D/L today: |
14,049 files (4,042M bytes) |
| Messages: | 2,456,569 |
| Posted today: | 1 |