Forums before death by AOL, social media and spammers... "We can't have nice things"
|    sci.logic    |    Logic -- math, philosophy & computationa    |    262,912 messages    |
[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]
|    Message 262,118 of 262,912    |
|    olcott to All    |
|    Turing-machine deciders a precise defini    |
|    23 Dec 25 09:34:19    |
   
   XPost: comp.theory, sci.math, comp.ai.philosophy   
   From: polcott333@gmail.com   
      
   A Turing-machine decider is a Turing machine D that   
   computes a total function D : Σ∗ → {Accept,Reject},   
   where Σ∗ is the set of all finite strings over the   
   input alphabet. That is:   
      
   1. Totality: For every finite string input w ∈ Σ∗,   
   D halts and outputs either Accept or Reject.   
      
   2. Decision basis: Each input string is evaluated   
   according to one of two types of properties:   
      
    (a) Syntactic property: a property of the input   
    string itself, such as containing a particular   
    substring or satisfying a structural pattern.   
      
    (b) Semantic property: a property of the sequence of   
    computational steps explicitly encoded by the input   
    string, i.e., the behavior that the input itself   
    specifies when interpreted as a machine description.   
      
   The decider outputs Accept if the corresponding property   
   holds for the input and Reject otherwise.   
      
   --   
   Copyright 2025 Olcott
|
[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]
(c) 1994, bbs@darkrealms.ca