Re: Rado's Sigma and the Halting Problem for Programs
From: David Bernier (david250_at_videotron.ca)
Date: 08/14/04
- Next message: Babylonian_Astrologer: "Re: Short Self-Reference Puzzle"
- Previous message: Simon G Best: "Re: What is the Result from Invoking this Halt Function?"
- In reply to: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Next in thread: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Messages sorted by: [ date ] [ thread ]
Date: Sat, 14 Aug 2004 01:06:06 -0400
r.e.s. wrote:
> "Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote ...
>
>>r.e.s. wrote:
>>
>>>"Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote ...
>>>
>>>>Technically, languages that can't interpret
>>>>themselves are said to be /not Turing-complete/.
>>
>>[...which ought to say that if L can't interpret itself, then
>>it is not TC; but not the other way around.]
>>
>>
>>>An interesting question concerns the converse of that.
>>>That is ...
>>>Can a universal M-program exist if M is *not* Turing-complete?
>>>(Universal here means universal within M; i.e. an M-program U
>>>is universal if U can simulate an arbitrary M-program.)
>>
>> Trivially! Consider the language SIMPLE, for example...
>
> -snip-
>
>>The Universal SIMPLE Program is therefore
>>
>> BEGIN
>> STOP
>> END
>
>
> When I introduced
> "programming model M (which is to include i/o conventions)",
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> the intent, of course, was that nontrivial i/o be part of the
> model. If "'no i/o' is a kind of i/o" is an i/o convention,
> then we'll certainly have some trivial models. (It could
> turn out that there are other near-trivial examples answering
> the question anyway.)
>
> On this topic -- problems with lack of i/o conventions -
> the difficulties discussed in the article
> www2.math.uic.edu/~jbaldwin/pub/cafom.ps
> seem quite serious, if I understand correctly. For example,
> how can Wolfram's Rule 110 CA be said to "simulate" a UTM, if
> there's no convention for identifying the UTM's halting state?
TM-language is at a lower level than any assembler language.
On the other hand, with quite some effort, it should be
possible to write a C program whose input is a sequence
of assembler op-codes, register values, main memory plus
additional op-codes for "print to screen" and whose
output would be a TM-language program translation
that is runnable. The initial TM tape state could be
divided in an op-codes segment, registers segment,
main memory segment, screen segment, etc.
So, starting from an assembly language program (including
op-codes for "print to screen", which I believe
don't exist in real processors), and a register
and main memory description, the high-level
C program would translate all this into
a runnable (i.e. simulatable) TM-language program.
It sure looks like a big undertaking.
David Bernier
- Next message: Babylonian_Astrologer: "Re: Short Self-Reference Puzzle"
- Previous message: Simon G Best: "Re: What is the Result from Invoking this Halt Function?"
- In reply to: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Next in thread: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
