Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #39920

Re: Is it possible to create a simple infinite emulation detector? [ cite sources ]

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Is it possible to create a simple infinite emulation detector? [ cite sources ]
Date 2021-09-25 22:54 +0100
Organization A noiseless patient Spider
Message-ID <878rzkuxrk.fsf@bsb.me.uk> (permalink)
References (4 earlier) <no2dnRC5q77teND8nZ2dnUU7-KnNnZ2d@giganews.com> <jNt3J.21983$nh7.14432@fx22.iad> <j6KdneWvdK9t7NP8nZ2dnUU7-VnNnZ2d@giganews.com> <87ee9cwhwe.fsf@bsb.me.uk> <SxM3J.23727$nh7.4164@fx22.iad>

Show all headers | View raw


Richard Damon <Richard@Damon-Family.org> writes:

> On 9/25/21 3:54 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> I derive a unique mapping from an input finite string to a Boolean
>>> value.
>> 
>> But is it a function?  And is it a function from S* to {true, false}
>> (for some finite alphabet S)?  It might be, but since you only found out
>> what a function is a few months ago, it's wise to ask.
>> 
>> Your term "unique mapping from an input finite string to a Boolean
>> value" is what a coder would say.  It's not the same as a mathematician
>> saying "f: S* -> {true, false}".
>> 
>>> I currently need static local data to do this, none-the-less a 
>>> unique mapping is derived. I can't understand how this is computable
>>> in C and not computable in a TM.
>> 
>>   _Bool f(char *s) { return s; }
>> 
>> is a C function that maps finite strings input strings to Boolean
>> values.  It has no corresponding TM.
>
> Actually, you should be able to map that. The key is you need to define
> how you encode character strings.
>
> If the tape allows 257 values per cell, corresponding to 'no value' or
> the ascii values 0-255, then the test is just is the cell we start at
> the 'no value', which is the equivalent for a null pointer, and return
> false/0 if it is, else return true.

OK, not the best example since you might consider that a natural
correspondence.  I'd suggest, then,

  _Bool f(char *s) { return (uintptr_t)s & 1; }

or

  _Bool f(char *s) { return ((uintptr_t)s + (uintptr_t)f) & 0x8800; }

or

  _Bool f(char *s) { return s && *s ? f(s+1) : (uintptr_t)&s & 1; }

> There is almost ALWAYS a 'mapping' issue of how do you plan to represent
> the various representations in one space to another.

Maybe.  I think we may disagree about what a "corresponding TM" really
is.  But that's not the main point I was trying to make: PO's words were
just too vague to address why he's puzzled that something "computable"
in C is not "computable" by a TM.

I agree that we can often define away the issue by being more specific.
The result is then a well-defined function that is can be implemented in
both C and realised as a TM, but lots of C code has no natural
corresponding TM (as I see it).

Also, I just wanted to reiterate why C is such a terrible choice, and
x86 code (RDRAND, anyone?) is even worse, as a formal model of
computation.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Is it possible to create a simple infinite emulation detector? olcott <NoOne@NoWhere.com> - 2021-09-23 13:30 -0500
  Re: Is it possible to create a simple infinite emulation detector? André G. Isaak <agisaak@gm.invalid> - 2021-09-23 19:17 -0600
    Re: Is it possible to create a simple infinite emulation detector? olcott <NoOne@NoWhere.com> - 2021-09-23 20:25 -0500
      Re: Is it possible to create a simple infinite emulation detector? André G. Isaak <agisaak@gm.invalid> - 2021-09-23 19:58 -0600
        Re: Is it possible to create a simple infinite emulation detector? olcott <NoOne@NoWhere.com> - 2021-09-23 22:13 -0500
          Re: Is it possible to create a simple infinite emulation detector? Richard Damon <Richard@Damon-Family.org> - 2021-09-23 23:25 -0400
          Re: Is it possible to create a simple infinite emulation detector? André G. Isaak <agisaak@gm.invalid> - 2021-09-23 21:38 -0600
      Re: Is it possible to create a simple infinite emulation detector? Richard Damon <Richard@Damon-Family.org> - 2021-09-23 22:14 -0400
  Re: Is it possible to create a simple infinite emulation detector? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-24 02:42 +0100
    Re: Is it possible to create a simple infinite emulation detector? olcott <NoOne@NoWhere.com> - 2021-09-23 21:01 -0500
      Re: Is it possible to create a simple infinite emulation detector? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-24 03:03 +0100
  Re: Is it possible to create a simple infinite emulation detector? Richard Damon <Richard@Damon-Family.org> - 2021-09-23 22:09 -0400
    Re: Is it possible to create a simple infinite emulation detector? olcott <NoOne@NoWhere.com> - 2021-09-23 22:27 -0500
      Re: Is it possible to create a simple infinite emulation detector? Richard Damon <Richard@Damon-Family.org> - 2021-09-23 23:39 -0400
        Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-24 09:49 -0500
          Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-24 21:54 +0100
            Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-24 16:53 -0500
              Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 00:22 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-24 19:01 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 21:43 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 15:47 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 22:24 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 17:51 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 00:55 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 22:00 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-26 06:26 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 15:30 +0100
          Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-24 20:09 -0400
            Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-24 19:48 -0500
              Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-24 21:27 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-24 20:52 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-24 22:27 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-24 22:36 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-24 23:31 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 06:06 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 09:09 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 12:09 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 11:18 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 12:24 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 06:03 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 08:58 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 10:07 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 09:18 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 12:14 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Mr Flibble <flibble@reddwarf.jmc> - 2021-09-25 18:54 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Jeff Barnett <jbb@notatt.com> - 2021-09-25 12:17 -0600
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 14:02 -0500
              Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 20:54 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 15:07 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 22:15 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 16:30 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 17:30 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 22:54 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 18:14 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 22:13 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 14:57 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 17:59 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 00:33 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 21:45 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-26 06:32 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 15:20 +0100
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-25 21:18 -0400
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] olcott <NoOne@NoWhere.com> - 2021-09-25 22:03 -0500
                Re: Is it possible to create a simple infinite emulation detector? [ cite sources ] Richard Damon <Richard@Damon-Family.org> - 2021-09-26 06:39 -0400

csiph-web