Groups | Search | Server Info | Login | Register
Groups > comp.software-eng > #3759
| From | olcott <polcott333@gmail.com> |
|---|---|
| Newsgroups | comp.theory, sci.logic, comp.software-eng, sci.math |
| Subject | Exactly what are deciders in the theory of computation? |
| Date | 2026-01-07 15:29 -0600 |
| Organization | A noiseless patient Spider |
| Message-ID | <10jmj88$10tik$1@dont-email.me> (permalink) |
| References | (1 earlier) <a3bcd46bf5b5a3ccc4b1308d8c7065008c1b4092.camel@gmail.com> <10hcu82$1d9h7$1@solani.org> <dbe9c3aa-42f9-496d-9394-a2d3205f9138@gmail.com> <10jiem1$3j7nf$1@dont-email.me> <10jli6i$k6rl$1@dont-email.me> |
Cross-posted to 4 groups.
On 1/7/2026 6:05 AM, Mikko wrote:
> On 06/01/2026 09:47, dart200 wrote:
>
> ...
>
>> i think the actual problem is the TM computing is not sufficient to
>> describe all computable relationships.
>
> It is not. Although we don't know any way compute what is not Turing
> computable,
In computability theory, a decider is a Turing machine
that halts for every input.[1] A decider is also called
a total Turing machine[2] as it represents a total function.
Because it always halts, such a machine is able to
decide whether a given string is a member of a formal
language. The class of languages that can be decided
by such machines is the set of recursive languages.
Given an arbitrary Turing machine, determining whether
it is a decider is an undecidable problem. This is a
variant of the halting problem, which asks for whether
a Turing machine halts on a specific input.
https://en.wikipedia.org/wiki/Decider_(Turing_machine)
That seems a little silly because a TM that simply
halts on all inputs including the empty string is
said to have accepted that input. The "decision" in
this case is "don't make any decision, just accept".
*Here is a better definition by a*
https://yuvalfilmus.cs.technion.ac.il/
*PhD computer science Associate Professor*
Yuval Filmus
Intuitively, a decider should be a Turing machine that
given an input, halts and either accepts or rejects,
relaying its answer in one of many equivalent ways,
such as halting at an ACCEPT or REJECT state, or leaving
its answer on the output tape.
https://cs.stackexchange.com/questions/84433/what-is-decider
Here is my own generalization across models
of computation.
All deciders essentially: Transform finite string
inputs by finite string transformation rules into
{Accept, Reject} values.
Thus the simple way to determine what is not
computable is that any required result that
cannot be derived by applying finite string
transformation rules to specific inputs is
outside the scope of computation.
From this frame-of-reference "undecidability"
is not actual weakness or limit to computation.
It is merely forming a requirement that exceeds
the boundary of the scope of computation.
> we can image a machine that can compute what a Turing
> machine can't. Such machine can use a tape as an input and output
> device as well as working storage just like Turing machine but has
> additional instructions for operations that are not Turring computable.
> While it is possible to imagine a halting decider for TUring machines
> implemented with an extended machine, a halting decider for all such
> machines still requires that the decider can compute something that
> none of the machines in its input domain can.
>
--
Copyright 2026 Olcott<br><br>
My 28 year goal has been to make <br>
"true on the basis of meaning expressed in language"<br>
reliably computable.<br><br>
This required establishing a new foundation<br>
Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar
Re: Proof that the halting problem itself is a category error polcott <polcott333@gmail.com> - 2025-12-10 17:03 -0600
Re: Proof that the halting problem itself is a category error wij <wyniijj5@gmail.com> - 2025-12-11 07:10 +0800
Re: Proof that the halting problem itself is a category error --- typo polcott <polcott333@gmail.com> - 2025-12-10 17:53 -0600
Re: Proof that the halting problem itself is a category error Oleksiy Gapotchenko <alex.s.gap@gmail.com> - 2026-01-06 01:24 +0100
Re: Proof that the halting problem itself is a category error olcott <polcott333@gmail.com> - 2026-01-05 18:39 -0600
is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-05 23:47 -0800
Re: is the ct-thesis cooked? olcott <polcott333@gmail.com> - 2026-01-06 19:26 -0600
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-06 19:03 -0800
Re: is the ct-thesis cooked? olcott <polcott333@gmail.com> - 2026-01-06 22:33 -0600
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-07 00:56 -0800
yes/no questions lacking a correct yes/no answer are incorrect questions olcott <polcott333@gmail.com> - 2026-01-07 05:50 -0600
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-12 07:12 -0500
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-12 07:06 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-12 14:09 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-12 22:16 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-12 20:21 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-13 07:09 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-13 12:33 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-14 22:43 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-15 04:23 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-15 22:28 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-16 01:08 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-16 11:46 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-16 14:21 -0800
The essence of all Computation generically defined olcott <polcott333@gmail.com> - 2026-01-16 16:58 -0600
Re: The essence of all Computation generically defined Richard Damon <Richard@Damon-Family.org> - 2026-01-16 18:21 -0500
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-16 18:21 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-16 16:43 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-16 22:24 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-16 23:23 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-17 07:33 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-17 19:14 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-17 22:28 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-17 22:05 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-18 07:05 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-18 10:15 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-18 15:56 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-18 13:50 -0800
Re: is the ct-thesis cooked? Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-18 22:27 +0000
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-18 15:01 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-18 19:28 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-18 20:30 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-20 00:29 -0500
Re: is the ct-thesis cooked? Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-18 22:28 +0000
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-18 19:28 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-18 20:51 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-20 00:29 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-19 22:18 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-20 07:59 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-20 17:55 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-24 09:44 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 14:36 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-24 19:52 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 18:24 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-25 13:21 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-25 13:05 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-25 17:36 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-25 21:56 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-26 11:39 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-26 11:43 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-26 17:17 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-26 14:29 -0800
Re: is the ct-thesis cooked? Dude <punditster@gmail.com> - 2026-01-27 13:31 -0800
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-28 01:12 -0800
Re: is the ct-thesis cooked? Dude <punditster@gmail.com> - 2026-01-28 13:29 -0800
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-28 13:37 -0800
Re: is the ct-thesis cooked? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-01-27 14:07 -0800
Re: is the ct-thesis cooked? Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-28 07:23 -0500
Re: is the ct-thesis cooked? Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-17 12:17 +0000
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-17 08:15 -0500
Re: is the ct-thesis cooked? dart200 <user7160@newsgrouper.org.invalid> - 2026-01-17 09:47 -0800
Re: is the ct-thesis cooked? Richard Damon <Richard@Damon-Family.org> - 2026-01-17 15:31 -0500
The essence of all Computation generically defined olcott <polcott333@gmail.com> - 2026-01-16 18:35 -0600
Re: is the ct-thesis cooked? Mikko <mikko.levanto@iki.fi> - 2026-01-07 14:05 +0200
Exactly what are deciders in the theory of computation? olcott <polcott333@gmail.com> - 2026-01-07 15:29 -0600
Re: is the ct-thesis cooked? PLO olcott <polcott333@gmail.com> - 2026-01-24 17:06 -0600
Re: is the ct-thesis cooked? PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-24 19:52 -0500
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 18:05 -0800
Re: is the ct-thesis cooked? PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-25 13:23 -0500
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-25 13:04 -0800
Re: is the ct-thesis cooked? PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-25 17:40 -0500
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-25 22:50 -0800
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-26 01:35 -0800
Re: is the ct-thesis cooked? PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-26 11:43 -0500
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-26 11:45 -0800
Re: is the ct-thesis cooked? PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-26 17:28 -0500
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-27 00:00 -0800
Re: is the ct-thesis cooked? PLO olcott <polcott333@gmail.com> - 2026-01-24 20:35 -0600
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 18:38 -0800
Re: is the ct-thesis cooked? PLO olcott <polcott333@gmail.com> - 2026-01-24 20:53 -0600
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 19:12 -0800
Re: is the ct-thesis cooked? PLO olcott <polcott333@gmail.com> - 2026-01-24 21:42 -0600
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 20:03 -0800
Re: is the ct-thesis cooked? PLO olcott <polcott333@gmail.com> - 2026-01-24 22:06 -0600
Re: is the ct-thesis cooked? PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 21:45 -0800
Re: Proof that the halting problem itself is a category error Mikko <mikko.levanto@iki.fi> - 2026-01-06 15:23 +0200
Boiling Gödel's 1931 Incompleteness proof down to its barest essence olcott <polcott333@gmail.com> - 2026-01-06 08:02 -0600
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence Mikko <mikko.levanto@iki.fi> - 2026-01-07 14:10 +0200
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence olcott <polcott333@gmail.com> - 2026-01-07 07:06 -0600
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence Mikko <mikko.levanto@iki.fi> - 2026-01-08 12:21 +0200
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence olcott <polcott333@gmail.com> - 2026-01-08 08:18 -0600
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence Mikko <mikko.levanto@iki.fi> - 2026-01-10 11:25 +0200
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence olcott <polcott333@gmail.com> - 2026-01-11 08:32 -0600
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-11 16:16 +0000
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence olcott <NoOne@NoWhere.com> - 2026-01-11 21:00 -0600
Re: Boiling Gödel's 1931 Incompleteness proof down to its barest essence Mikko <mikko.levanto@iki.fi> - 2026-01-12 13:05 +0200
csiph-web